[已解决]带你学c带你飞测试题第2 题

不知君

#include<stdio.h>
#include<math.h>

int main()
{
        long long a,b,c,i;
        b=1;
        while(b!=600851475143)
        {
                a=2;
                i=1;
                for(;i<=a-1;i++,a++)
                {
                        if(a%i==0)
                        {
                                c=a;
                                b=b*a;
                        }
                }
        }
        printf("600851475143最大质数为%lld\n",c);
        return 0;
       
}
和小甲鱼的解题思路不同，但运行不了，想知道为啥

最佳答案

月排行榜 / 总排行榜

傻眼貓咪

2022-4-23 15:21:31

不知君 发表于 2022-4-23 17:20
大佬，就是这种情况，应该用怎么样的思路呢

反向思路，一般都会先判断因数，再判断是否为质数，这样做只会重复很多次同样的循环。
可以试试先找质数，从 2 开始，再判断是否是因数（与 600851475143 除整）便可。

#include <stdio.h>

int isPrime (int n) {
    if (n == 2 || n == 3) return 1;
    for (int i = 2; i * i < n; i++) {
        if (!(n % i)) return 0;
    }
    return 1;
}

int foo (long long n) {
    int prime = 2;
    while (n > 1) {
        while (!(n % prime)) {
            n /= prime;
        }
        if (n == 1) break;
        do {
            prime++;
        } while (!isPrime(prime));
    }
    return prime;
}

int main()
{
    printf("%d", foo(600851475143));

    return 0;
}

跳转到最佳答案楼层

傻眼貓咪

不知君 发表于 2022-4-23 17:20
大佬，就是这种情况，应该用怎么样的思路呢

反向思路，一般都会先判断因数，再判断是否为质数，这样做只会重复很多次同样的循环。
可以试试先找质数，从 2 开始，再判断是否是因数（与 600851475143 除整）便可。

#include <stdio.h>

int isPrime (int n) {
    if (n == 2 || n == 3) return 1;
    for (int i = 2; i * i < n; i++) {
        if (!(n % i)) return 0;
    }
    return 1;
}

int foo (long long n) {
    int prime = 2;
    while (n > 1) {
        while (!(n % prime)) {
            n /= prime;
        }
        if (n == 1) break;
        do {
            prime++;
        } while (!isPrime(prime));
    }
    return prime;
}

int main()
{
    printf("%d", foo(600851475143));

    return 0;
}

傻眼貓咪

首先，你先要明白为什么这么多数字不用，偏偏要用 600851475143 这个数字？
因为这个数字足够大，其质数因子也相当大，这表示一般算法肯定不通，循环肯定超时（你试想想，需要循环多少次？）

不知君

傻眼貓咪 发表于 2022-4-23 16:13
首先，你先要明白为什么这么多数字不用，偏偏要用 600851475143 这个数字？
因为这个数字足够大，其质数因 ...

大佬，就是这种情况，应该用怎么样的思路呢

yushenga

前来学习

不知君

傻眼貓咪 发表于 2022-4-23 17:42
反向思路，一般都会先判断因数，再判断是否为质数，这样做只会重复很多次同样的循环。
可以试试先找质 ...

好的