HDOJ(HDU) 2136 Largest prime factor(素数筛选)-阿里云开发者社区

开发者社区> 云计算> 正文
登录阅读全文

HDOJ(HDU) 2136 Largest prime factor(素数筛选)

简介: Problem Description Everybody knows any number can be combined by the prime number. Now, your task is telling me what position of the largest prime factor.

Problem Description
Everybody knows any number can be combined by the prime number.
Now, your task is telling me what position of the largest prime factor.
The position of prime 2 is 1, prime 3 is 2, and prime 5 is 3, etc.
Specially, LPF(1) = 0.

Input
Each line will contain one integer n(0 < n < 1000000).

Output
Output the LPF(n).

Sample Input
1
2
3
4
5

Sample Output
0
1
2
1
3

题目大意:每个素数在素数表中都有一个序号,设1的序号为0,则 2
的序号为1(4是2的倍数,所以4的序列也是1),3的序号为2,5的序号为3,以此类推。现在要求输出 所
给定的数n的最大质因子的序号,0 < n < 1000000。

思路:巧用素数打表法。用sum计算素数的序号,将素数连同他的倍数一起置为它的素数序号, 从小到大循环, 这样数组里存放的序号就是最大素数因子的序号了。
注意:初始化时令所有数为0。
再通过sum计算累加,改变之后primeNum[i]为 数 i的最大素数因子的序号。


import java.util.Arrays;
import java.util.Scanner;

public class Main{
    static int primeNum[] = new int[1000002];

    public static void main(String[] args) {
        dabiao();
        Scanner sc = new Scanner(System.in);
        while (sc.hasNext()) {
            int n = sc.nextInt();
            System.out.println(primeNum[n]);
        }
    }

    private static void dabiao() {
        int sum = 1;
        Arrays.fill(primeNum, 0);
        for (int i = 2; i < primeNum.length; i++) {
            if (primeNum[i] == 0) {
                for (int j = i; j < primeNum.length; j = j + i) {
                    primeNum[j] = sum;
                }
                sum++;
            }
        }
    }
}

版权声明:本文内容由阿里云实名注册用户自发贡献,版权归原作者所有,阿里云开发者社区不拥有其著作权,亦不承担相应法律责任。具体规则请查看《阿里云开发者社区用户服务协议》和《阿里云开发者社区知识产权保护指引》。如果您发现本社区中有涉嫌抄袭的内容,填写侵权投诉表单进行举报,一经查实,本社区将立刻删除涉嫌侵权内容。

分享: