挑战程序竞赛系列(14):2.6素数

版权声明:本文为博主原创文章,未经博主允许不得转载。 https://blog.csdn.net/u014688145/article/details/73536732

挑战程序竞赛系列(14):2.6素数

详细代码可以fork下Github上leetcode项目,不定期更新。

练习题如下:

AOJ 0009: Prime Number

非常easy,素数就是从最小数开始生成的,它的倍数都不是素数,应该说这是素数最本源的定义了。

代码如下:(艾氏筛法)

public static void main(String[] args) throws NumberFormatException, IOException{
        int MAX = 1000000;
        boolean[] isPrime = new boolean[MAX];
        int[] prime = new int[MAX];
        Arrays.fill(isPrime, true);
        isPrime[0] = isPrime[1] = false;
        for (int i = 2, k = 0; i < MAX; ++i){
            if (isPrime[i]){
                k++;
                for (int j = 2 * i; j < MAX; j +=i){
                    isPrime[j] = false;
                }
            }
            prime[i] = k;
        }
        BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
        String str;
        while ((str=br.readLine())!=null){
            System.out.println(prime[Integer.parseInt(str)]);
        }
    }

POJ 3126: Prime Path

思路:艾氏筛选+BFS,起初做法是暴力BFS,不管三七二十一,把所有符合条件的素数加入队列中,结果运行即慢,在OJ上还MLE了,后来才发现BFS也可以剪枝。剪枝的方法:用dp记录到达当前素数的路径长度,如果先前已经抵到过了,则不再需要加入队列。

代码如下:

    /**
     * bfs + seive
     * @param args
     * @throws IOException
     */
    public static void main(String[] args) throws IOException {
        Scanner in = new Scanner(System.in);
        seive();
        int N = in.nextInt();
        for (int i = 0; i < N; ++i){
            int from = in.nextInt();
            int to = in.nextInt();
            System.out.println(solve(from, to));
        }
    }

    static int MAX = 9999 + 16;
    static boolean[] isPrime;

    public static void seive(){
        isPrime = new boolean[MAX];
        Arrays.fill(isPrime, true);
        isPrime[0] = isPrime[1] = false;
        for (int i = 2; i < MAX; ++i){
            if (isPrime[i]){
                for (int j = 2 * i; j < MAX; j += i){
                    isPrime[j] = false;
                }
            }
        }
    }

    public static int solve(int from, int to){
        Queue<Integer> queue = new LinkedList<Integer>();
        queue.offer(from);
        int[] dp = new int[MAX];
        Arrays.fill(dp, 1 << 30);
        dp[from] = 0;
        while (!queue.isEmpty()) {
            int prime = queue.poll();
            for (int j = 0; j < 4; ++j) {
                for (int k = 0; k < 10; ++k) {
                    int next = next(prime, j, k);
                    if (next == prime || next < 1000 || !isPrime[next] || dp[next] <= dp[prime])
                        continue;
                    dp[next] = dp[prime] + 1;
                    queue.offer(next);
                }
            }
        }
        return dp[to];
    }

    public static int next(int prime, int digit, int change){
        switch (digit) {
        case 0:
            return prime / 10 * 10 + change;
        case 1:
            return prime / 100 * 100 + prime % 10 + change * 10;
        case 2:
            return prime / 1000 * 1000 + prime % 100 + change * 100;
        case 3:
            return prime % 1000 + change * 1000;
        }
        return 0;
    }

POJ 3421: X-factor Chains

唉,也不知道是在考阅读理解,还是真的学算法,理解了半天都不知道它到底说的啥意思,题目真的太含糊。实际上是求:一个数的质因子个数,及这些质因子组成数列的排列组合,顺序无所谓,但要考虑重复质因子。

公式:

排列数=n!∏ki=1ni!

排列数 = \frac{n!}{\prod_{i = 1}^k n_i !} 其中,n表示所有质因数的个数,nin_i表示,每个质因子的出现的个数。 如:

100: {2 = 2},{5 = 2}

并没有使用PollardRho算法,暴力做法也有O(n√)O(\sqrt n),num在2202^{20}范围内,此题够了。

代码如下:

public static void main(String[] args) throws IOException {
        Scanner in = new Scanner(System.in);
        while (in.hasNext()){
            int num = in.nextInt();
            System.out.println(solve(num));
        }
        in.close();
    }

    public static String solve(int num){
        Map<Integer, Integer> factors = primeFactor(num);
        long max = 0;
        for (int key : factors.keySet()){
            max += factors.get(key);
        }
        long cnt = 1;
        for (int key : factors.keySet()){
            cnt *= factor(factors.get(key));
        }
        cnt = factor(max) / cnt;
        return max + " " + cnt;
    }

    public static long factor(long n){
        long res = 1;
        for (long i = 1; i <= n; ++i){
            res *= i;
        }
        return res;
    }

    public static Map<Integer,Integer> primeFactor(int num){
        Map<Integer, Integer> factors = new HashMap<Integer, Integer>();
        for (int i = 2; i * i <= num; ++i){
            while (num % i == 0){
                if (!factors.containsKey(i)) factors.put(i, 0);
                factors.put(i, factors.get(i) + 1);
                num = num / i;
            }
        }
        if (num != 1){
            factors.put(num, 1);
        }
        return factors;
    }

POJ 3292: Semi-prime H-numbers

思路:艾氏筛选,接着合成hSemiPrime,这道题刚开始以为求出所有的hPrime之后,直接合成不会存在重复元素,所以用二分或者带方向的遍历就完事,可惜它居然存在重复元素!

代码如下:

public static int solve(int h){
        int cnt = 0;
        for (int i = 0; i <= h && prime[i] * prime[i] <= h; ++i){
            int rt = h;
            while (rt >= i && prime[i] * prime[rt] > h) rt--;
            cnt += (rt - i + 1);
        }
        return cnt;
    }

测试用例过不了(合成中存在重复元素,所以只能记录所有可能的hSemiPrime),这样的话,就在程序初始化时就全部算出来即可,再用accumalte,进行统计,简单。

代码如下:

    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        seive();
        while (true){
            int h = in.nextInt();
            if (h == 0) break;
            System.out.println(h + " " + accumalte[h]);
        }
        in.close();
    }

    static int MAX = 1000001 + 16;
    static boolean[]  hPrime;
    static long[] prime;
    static boolean[] hSemiPrime;
    static int[] accumalte;

    public static void seive(){
        hPrime = new boolean[MAX];
        prime = new long[MAX];

        for (int i = 0; i < MAX; ++i){
            if (i % 4 != 1) hPrime[i] = false;
            else hPrime[i] = true;
        }

        int k = 0;
        for (int i = 5; i < MAX; ++i){
            if (hPrime[i]){
                prime[k++] = i;
                for (int j = 2 * i; j < MAX; j += i){
                    hPrime[j] = false; 
                }
            }
        }

        hSemiPrime = new boolean[MAX+1];

        for (int i = 0; i < k; ++i){
            for (int j = i; j < k; ++j){
                if (prime[i] * prime[j] > MAX) break;
                hSemiPrime[(int)(prime[i] * prime[j])] = true;
            }
        }

        accumalte = new int[MAX+1];
        for (int i = 1; i < accumalte.length; ++i){
            if (hSemiPrime[i]) accumalte[i] = accumalte[i-1] + 1;
            else accumalte[i] = accumalte[i-1];
        }
    }

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

扫码关注云+社区

领取腾讯云代金券