[已解决]求解质数问题

超越大神

1. #include<stdio.h>
   
2. int main(void)
   
3. {
   
4.     long long a=600851475143,i,b,k,flag,j;
   
5.         for(i=2;i<a;i++)
   
6.         {
   
7.                 b=a%i;
   
8.                 if(b==0)
   
9.                 {
   
10.                         j=a/i;
    
11.                         for(k=3;k<j;k++)
    
12.                         {
    
13.                                 if(j%k==0) break;
    
14.                                 if(j==k+1) flag=1; //判断是否质数
    
15.                         }
    
16.                         if(flag=1)
    
17.                     {
    
18.                              printf("%lld",j);break;
    
19.                     }
    
20.                 }
    
21.         }
    
22.         return 0;
    
23. }

复制代码

求解的一直和小甲鱼老师求的不一样，但是我看代码差不多。
小甲鱼代码

1. #include <stdio.h>
   
2. #include <math.h>
   
3. 
   
4. int main()
   
5. {
   
6.         long long i, j, k, l, num = 600851475143;
   
7.        int  flag = 1;
   
8. 
   
9.         for (i = 2, j = num/i; flag != 0; i++, j = num/i, flag = 1)
   
10.         {
    
11.                 if (i * j == num)
    
12.                 {
    
13.                         k = sqrt((double)j);
    
14.                         for (l = 2; l <= k; l++)
    
15.                         {
    
16.                                 if (j % l == 0)
    
17.                                 {
    
18.                                         flag = 0;
    
19.                                         break;
    
20.                                 }
    
21.                         }
    
22.                         if (flag)
    
23.                         {
    
24.                                 break;
    
25.                         }
    
26.                 }
    
27.         }
    
28. 
    
29.         printf("%lld\n", i);
    
30. 
    
31.         return 0;
    
32. }

复制代码

最佳答案

月排行榜 / 总排行榜

jackz007

2020-11-17 14:38:39

超越大神 发表于 2020-11-17 14:29
太复杂了，这个题目求的是最大质数因子问题，只要从2开始除就行了，只要能得到质数，那就是最大的；但是 ...

        先看看结果 6857 是不是正确的
        其实，这个代码也不复杂，核心函数就是 decom(long long * x , long long * y , long long n) ，这个函数把 n 分解成 * x 乘以 * y，两个因数中，* x 小，* y 大，而且 * x 一定是质数因子，如果 n 可以被分解，函数就会返回 1，否则，就返回 0，我们只要让 * y 成为新的 n，不停地分解下去，到不能继续分解的时候， n 就是最大的质数因子了。

跳转到最佳答案楼层

jackz007

       楼主的代码写复杂了

1. #include<stdio.h>
   
2. 
   
3. int main(void)
   
4. {
   
5.         long long a = 600851475143 , b , i , flag  ;
   
6.         for(flag = 1 , i = 2 ; i * i < a + 1 ; i ++) {  // flag = 1 ，先假定 a 是质数
   
7.                 if(a % i == 0) {                        // 如果 a 可以整除 i
   
8.                         flag = 0                   ;    // 那 a 就不是质数
   
9.                         break                      ;    // 没必要继续循环了
   
10.                 }
    
11.         }
    
12.         if(flag == 1) printf("%I64d 是质数\n" , a) ;    // 循环中 flag 没有被修改，a 显然就是质数了。
    
13.         else printf("%I64d 不是质数\n" , a)        ;
    
14. }

复制代码

超越大神

jackz007 发表于 2020-11-17 10:54
楼主的代码写复杂了

我表达有误。问题是
编写一个程序，求解 600851475143 的最大质数因子是多少
每个合数都可以写成几个质数（素数）相乘的形式，这几个质数就都叫做这个合数的质数因子。
比如 13195 的质数因子有 5, 7, 13 和 29

jackz007

超越大神 发表于 2020-11-17 12:08
我表达有误。问题是
编写一个程序，求解 600851475143 的最大质数因子是多少
每个合数都可以写成几个质 ...

那就稍微复杂一点

1. #include <stdio.h>
   
2. 
   
3. int decom(long long * x , long long * y , long long n)
   
4. {
   
5.         int r                         ;
   
6.         long long i , j , k           ;
   
7.         for(r = 0 , i = 2 ; i * i < n + 1 ; i ++) {
   
8.                 if(i < n && ! (n % i)) {
   
9.                         * x = i       ;
   
10.                         * y = n / i   ;
    
11.                         r = 1         ;
    
12.                         break         ;
    
13.                 }
    
14.         }                       
    
15.         return r                      ;
    
16. }
    
17. 
    
18. main(void)
    
19. {
    
20.         long long a = 600851475143 , b , c , i , j  ;
    
21.         printf("%I64u = " , a)                      ;
    
22.         for(b = a , c = 0 ; decom(& i , & j , b) ; b = j , c ++) {
    
23.                 if(c) printf(" * ")                 ;
    
24.                 printf("%I64d" , i)                 ;
    
25.         }
    
26.         printf(" * %I64d\n" , b)                    ;
    
27.         printf("the anwser is : %d\n" , b)          ;
    
28. }

复制代码

       编译、运行实况：

1. D:\0002.Exercise\C>g++ -o x x.c
   
2. 
   
3. D:\0002.Exercise\C>x
   
4. 600851475143 = 71 * 839 * 1471 * 6857
   
5. the anwser is : 6857
   
6. 
   
7. D:\0002.Exercise\C>

复制代码

超越大神

jackz007 发表于 2020-11-17 13:48
那就稍微复杂一点

       编译、运行实况：

太复杂了，这个题目求的是最大质数因子问题，只要从2开始除就行了，只要能得到质数，那就是最大的；但是我一直看不出来我写的到底哪里出问题了，逻辑应该没问题。

jackz007

超越大神 发表于 2020-11-17 14:29
太复杂了，这个题目求的是最大质数因子问题，只要从2开始除就行了，只要能得到质数，那就是最大的；但是 ...

        先看看结果 6857 是不是正确的
        其实，这个代码也不复杂，核心函数就是 decom(long long * x , long long * y , long long n) ，这个函数把 n 分解成 * x 乘以 * y，两个因数中，* x 小，* y 大，而且 * x 一定是质数因子，如果 n 可以被分解，函数就会返回 1，否则，就返回 0，我们只要让 * y 成为新的 n，不停地分解下去，到不能继续分解的时候， n 就是最大的质数因子了。

超越大神

jackz007 发表于 2020-11-17 14:38
先看看结果 6857 是不是正确的
        其实，这个代码也不复杂，核心函数就是 decom(long lo ...

不是的，这个问题求解的是最大的质数因子，然后我看了你的最后三项相乘之后得到的答案和我的相同但是小甲鱼答案比我的还小。