题目3：找出一个合数的最大质数因子

ietar

python 6857

取约数算法优化 只取质数 记录取到的约数 i  下次取约数从 i 开始
手写个轮子用来计时 优化效果很有限 可能要更大的数才见效


>>> timef(p3(),number=10000)
0.0010133860000109962
>>> timef(p3_mix(),number=10000)
0.000952252999979919

1. def p3_mix():
   
2.     import math
   
3.     a = 600851475143
   
4.     def p3_get_prime(n):
   
5.         return int(3*n+1+(math.sin(math.pi*n/2))**2)
   
6. 
   
7.     def is_prime(n):
   
8.         if not n%2:
   
9.             return False
   
10.         n1 = int(math.sqrt(n))
    
11.         for i in range(3,n1+1,2):
    
12.             if not n%i:
    
13.                 return False
    
14.         return True
    
15.    
    
16.     def p3_1_mix(n,num=1,i=2):
    
17.         if is_prime(n):
    
18.             return n
    
19.         while i < a//2+1:
    
20.             if not n%i:  # n被i整除
    
21.                 return p3_1_mix(n/i,num,i)
    
22.             else:  # n无法被i整除
    
23.                 if i == 2:
    
24.                     i = 3
    
25.                 elif i == 3:
    
26.                     i = p3_get_prime(num)
    
27.                 else:
    
28.                     num += 1
    
29.                     i=p3_get_prime(num)
    
30.     print(p3_1_mix(a))
    
31.                

复制代码

doodu

冷钟天 发表于 2016-7-4 15:57
n=600851475143
a=2
while n!=a:

1，为什么a递增以后的值，没有在素数范围内也行？？？
2，为什么不断缩小的n，不再使用比a小的值（素数）取商？？？

假如n初始为100，a初始为2：
      n            a
1， 100         2<--素数
2、 50          3<--素数
3、 50          4
4、 50          5<--素数
5， 10           6
6， 10           7<--素数
7， 10           8
8， 10           9
9， 10           10

11才是质数啊？？？

micolar

C 不知道为啥不稳定 难道是虚拟机的原因？

1. #include<stdio.h>
   
2. int a[1000001];
   
3. int main(){
   
4.         int i,j;
   
5.         for(i = 2; i <= 500000;i++){
   
6.                 for(j = i * 2;j <=1000000;j += i)
   
7.                         a[j] = 1;
   
8.         }
   
9.         for(i = 999999;i >= 2; i-- )
   
10.         if(a[i] == 0 && 600851475143%i == 0){
    
11.                 printf("%d",i);
    
12.                 return 0;
    
13.         }
    
14.        
    
15.         printf("600851475143");
    
16.        
    
17.         return 0;
    
18. }

复制代码

Weiwei7

% %Euler_3  What is the largest prime factor of the number 600851475143 ?
% % The prime factors of 13195 are 5, 7, 13 and 29.

x=input('please input a number\n');
l=0;
for i=3:2:x
    if isprime(i)==1 && mod(x,i)==0
            l=i;
            x=x/i;  
            disp(l);
    end         
end

永恒的蓝色梦想

1. num = 600851475143
   
2. divisor = 3
   
3. 
   
4. 
   
5. while num != 1:
   
6.     if num % divisor:
   
7.         divisor += 2
   
8.     else:
   
9.         num //= divisor
   
10. 
    
11. 
    
12. print(divisor)

复制代码

RRRex

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


int main()
{
    int begin_time, end_time;
    begin_time = clock();

    int biggest = 0;
    _Bool not_prime = 0;
    for (int i = 3; i < sqrt(600851475143); i += 2)
    {
        if (600851475143 % i == 0)
        {
            for (int j = 3; j < sqrt(i); j += 2)
            {
                if (i % j == 0)
                {
                    not_prime = 1;
                    break;
                }
            }
            if (!not_prime)
            {
                biggest = i;
            }
        }
    }
    printf("600851475143 的最大质数因子是%d\n", biggest);

    end_time = clock();
    printf("\n程序一共运行%dms\n", end_time - begin_time);

    return 0;
}

justjust001

1. #include <stdio.h>
   
2. #include <time.h>
   
3. 
   
4. int main()
   
5. {
   
6.         unsigned long long num = 600851475143;
   
7.         unsigned long long a, t;
   
8. 
   
9.         int begin = clock();
   
10.         for (a = 2; a < num; a++)
    
11.         {
    
12.                 for (t = 2; t < a / 2; t++)
    
13.                         if (a % t == 0)
    
14.                                 break;
    
15.                 if ( t >= a / 2)
    
16.                         if (num % a == 0)
    
17.                         {
    
18.                                 num /= a;
    
19.                                 a = 1;
    
20.                         }
    
21.         }
    
22.                
    
23.         printf("600851475143 最大质数因子 = %llu\n", num);
    
24.         int end = clock();
    
25.         printf("time = %dms\n", end - begin);
    
26.         system("pause");
    
27.         return 0;
    
28. }
    

复制代码

华博文

import re
import math
import time

method = re.compile("[^0-9]")
def forma(miao):
    tim = list()
    ge_m = float("{:.10f}".format(miao))
    ge_h = float("{:.10f}".format(ge_m / 3600))
    ge_h_guo = float("{:.10f}".format(miao % 3600))
    ge_f = float("{:.10f}".format(ge_h_guo / 60))
    ge_miao = float("{:.10f}".format(ge_h_guo % 60))
    if ge_h > 1:
        tim.append(int(ge_h))
    if ge_f > 1 or len(tim) != 0:
        tim.append(int(ge_f))
    tim.append(ge_miao)
    return tim



da = int()
ran = input("请输入一个整数 , 求最大的质数因子：")
tex = method.search(ran)
if not tex:
   
    ship = int(ran)#600851475143
    chu = int(math.sqrt(ship))
    time_start = time.perf_counter()
    tiger_chu = sorted([each for each in range(chu , 0 , -1) if ship % each == 0] , reverse = True)
    rabbit_zhi = [[car for car in range(2 , int(each)) if each % car == 0] for each in sorted(tiger_chu , reverse = True)]
    da = tiger_chu[rabbit_zhi.index([])]

    miao = time.perf_counter() - time_start
    lai = forma(miao)
    if len(lai) == 1:
        print("最大值为：" + str(da) + "\n运行时间为：{:.2f}秒".format(lai[0]))
    elif len(lai) == 2:
        print("最大值为：" + str(da) + "\n运行时间为：{}分{}秒".format(lai[0] , lai[1]))
    else:
        print("最大值为：" + str(da) + "\n运行时间为：{}时{}分{}秒".format(lai[0] , lai[1] , lai[2]))
else:
    print("您输入的数值运行不了~~")


#我感觉我的效率还不错，欢迎大家来copy~~

天云TY

1. import tkinter as tk
   
2. x = 600851475143
   
3. i = 2
   
4. while True:
   
5.    
   
6.     if i >= x:  #当i > x时，x铁定除不尽i(当i = x 时，它就没意义了)，所以执行下列命令：
   
7.         break
   
8.     while x % i == 0: #当x % i == 0
   
9.         if i >= x:  #当i > x时，x铁定除不尽i(当i = x 时，它就没意义了)，所以执行下列命令：
   
10.             break
    
11.         else:
    
12.             x /= i
    
13. 
    
14.     else:
    
15.         i += 1
    
16. s = tk.Tk();tk.Label(s,text=x).pack();s.mainloop() #显示出答案

复制代码

1666194196

#include <stdio.h>

void main(){
        //13195的所有质因数为5、7、13和29。
        //600851475143最大的质因数是？
        int i,a=13195,max=0;
        for(i=2;i<a;i++){//2到它本身-1的循环
                if(a%i==0){//如果能整除说明是他的因数
               
                        int j,flag=1;
                       
                        for(j=2;j<i;j++){//2到它本身-1的循环
                                if(i%j==0){//如果能整除说明有因数 ,标志为假 ，不输出
                                        flag=0;
                                }
                        }
                        if(flag){//如果没有能整除顺序执行下来flag=1，为真。打印出这个数
                                printf("质因数%d\n",i);
                                max=i;
                       
                        }
                }
        }
        printf("做大质因数=%d",max);
}

带上面具的孩纸

1. int main()
   
2. {
   
3.     unsigned long long int MPX;
   
4.     int MAX = 1;
   
5.     int i;
   
6. 
   
7.     printf("\nplease input number: ");
   
8.     scanf("%llu",&MPX);
   
9. 
   
10.     for(i = 2;i < MPX;i++)
    
11.     {
    
12.         if(MPX % i == 0)
    
13.         {
    
14.             MAX = MAX > i ? MAX : i;
    
15.            // printf("%d\t",i);
    
16.         }
    
17.     }
    
18.     printf("\n MAX=%d\n",MAX);
    
19. 
    
20.     return 0;
    
21. }

复制代码

如有错误 请指正

杨扬阳羊洋

1. unsigned long long isprime(unsigned long long num)
   
2. {
   
3.     unsigned long long max=0;
   
4.     for(unsigned long long i=2;i<=(int)sqrt((double)num);i++)
   
5.     {
   
6.         if( (num%i)==0 )  {return 0;}
   
7.     }
   
8.     return 1;
   
9. }
   
10. unsigned long long max_factor(unsigned long long num)
    
11. {
    
12.     unsigned long long max=0,temp=0;
    
13.     for(unsigned long long j=2;j<=(int)sqrt((double)num);j++)
    
14.     {
    
15.         int n=0;
    
16.         if(num%j==0)    // 找出合数中的因子
    
17.         {
    
18.             if( isprime(j)==1 )
    
19.             {
    
20.                 if(max<j){max=j;printf("prime=%llu\n",j);}
    
21.             }
    
22.             temp=num/j;
    
23.             if( isprime(temp)==1 )
    
24.             {
    
25.                 if(max<temp){max=temp;printf("prime=%llu\n",temp);}
    
26.             }
    
27.         }
    
28.     }
    
29.     return max;
    
30. }

复制代码

guoquanli

游客 218.17.207.x 发表于 2015-10-30 16:07
大数用了__int64类型

输出结果：

非常感谢您的分享，请教您一下，我在linux环境下运行您的这段代码提示：unknown  type  name '__int64',头文件<math.h>也包含了，问题在哪里了？

就是要努力呀

#include <stdio.h>
#include <time.h>

int main(void)
{
        int i = 2;
        long int a = 600851475143;
        time_t start, end;

        time(&start);

        while(a > 1)
        {
                if(a % i == 0)
                {
                        a /= i;

                        continue;
                }

                i++;
        }

        time(&end);

        printf("%ld的最大质因数为:%d\n", a, i);
        printf("time:%ld\n", end - start);

        return 0;
}
~                                                   

就是要努力呀

#include <stdio.h>
#include <time.h>

int main(void)
{
        int i = 2;
        long int a = 600851475143;
        time_t start, end;

        time(&start);

        while(a > 1)
        {
                if(a % i == 0)
                {
                        a /= i;
                }
                else i++;
        }

        time(&end);

        printf("600851475143的最大质因数为:%d\n", i);
        printf("time:%ld\n", end - start);

        return 0;
}

代号-K

这与第七题 类似，只做稍微修改即可得出答案 :6857

1. int calculatePrime(long long value)
   
2. {
   
3.     int array[100] = {0};
   
4.     array[0] = 2;
   
5.     int i = 1;
   
6.     int j = 3;
   
7.     int k = 0;
   
8.     int yes = 1;
   
9.     while(true)
   
10.     {
    
11.         if(array[i-1] >= value)
    
12.         {
    
13.             break;
    
14.         }
    
15.         else
    
16.         {
    
17.             k = 0;
    
18.             while( k < i)
    
19.             {
    
20.                 if(j % array[k] == 0)
    
21.                 {
    
22.                     yes = 0;
    
23.                     break;
    
24.                 }
    
25.                 k++;
    
26.             }
    
27.             if(yes && value % j == 0)
    
28.             {
    
29.                 value /= j;
    
30.                 array[i++] = j;
    
31.             }
    
32.         }
    
33.         j++;
    
34.         yes = 1;
    
35.     }
    
36.     return array[i-1];
    
37. }
    
38. 
    
39. int main(int argc, char *argv[])
    
40. {
    
41.     int sum = calculatePrime(600851475143);
    
42.     printf("%d\n",sum);
    
43.     return 0;
    
44. }

复制代码

永恒的蓝色梦想

C++ 0ms

1. #include<iostream>
   
2. #include<cmath>
   
3. #include<cstdint>
   
4. using namespace std;
   
5. 
   
6. 
   
7. 
   
8. uint64_t maxPrimeDivisor(uint64_t num) {
   
9.     if (num < 2) {
   
10.         return 0;
    
11.     }
    
12. 
    
13.     while (!(num & 1)) {
    
14.         num >>= 1;
    
15.     }
    
16. 
    
17.     if (num != 1) {
    
18.         uint64_t divisor = 3, max = sqrt(num);
    
19. 
    
20.         while (divisor <= max) {
    
21.             if (num % divisor) {
    
22.                 divisor += 2;
    
23.             }
    
24.             else {
    
25.                 do {
    
26.                     num /= divisor;
    
27.                 } while (!(num % divisor));
    
28. 
    
29.                 if (num == 1) {
    
30.                     return divisor;
    
31.                 }
    
32. 
    
33.                 max = sqrt(num);
    
34.             }
    
35.         }
    
36. 
    
37.         return num;
    
38.     }
    
39. 
    
40.     return 2;
    
41. }
    
42. 
    
43. 
    
44. 
    
45. int main() {
    
46.     ios::sync_with_stdio(false);
    
47. 
    
48.     cout << maxPrimeDivisor(600851475143) << endl;
    
49.     return 0;
    
50. }

复制代码

leon0149

71 839 1471 6857
0.002s

1. #include <stdio.h>
   
2. #include <math.h>
   
3. #include <stdlib.h>
   
4. 
   
5. #define NUM 600851475143        // 常量定义
   
6. 
   
7. int isPrime(int x){
   
8.     /*
   
9.      * 判断是不是素数
   
10.      */
    
11.     int ret = 1;
    
12.     for (int i = 3; i < sqrt(x); i+=2) {
    
13.         if (x % i == 0)
    
14.             ret = 0;
    
15.     }
    
16. 
    
17.     return ret;
    
18. }
    
19. 
    
20. int isPrimeLong(long long x){
    
21.     /*
    
22.      * 判断是不是素数
    
23.      */
    
24.     int ret = 1;
    
25.     long double sqr = sqrt(x);
    
26.     for (long i = 3; i < sqr; i+=2) {
    
27.         if (x % i == 0)
    
28.             ret = 0;
    
29.     }
    
30. 
    
31.     return ret;
    
32. }
    
33. 
    
34. int main(void)
    
35. {
    
36.     int *array = NULL;
    
37.     long long *array2 = NULL;
    
38.     double sqr = sqrt(NUM);
    
39.     int cnt = 0;
    
40.     int cnt2 = 0;
    
41. 
    
42.     for (int i = 3; i < sqr; i+=2) {
    
43.         /*
    
44.          * 把这个数据分成两部分
    
45.          */
    
46.         if (NUM % i == 0){
    
47.             /*
    
48.              * 判断能不能被这个数据整除
    
49.              */
    
50.             if (isPrime(i)){
    
51.                 /*
    
52.                  * 判断是不是素数
    
53.                  * 如果是
    
54.                  * 那么分配一个数据的内存
    
55.                  * 把这个素数放到数组array里面
    
56.                  */
    
57.                 array = (int *)realloc(array, sizeof(int));
    
58.                 array[cnt] = i;
    
59.                 cnt++;
    
60.             }
    
61.             long long num = NUM / i;    // 如果上面i可以被整除那么 一定有另一个数匹配这个i
    
62.             if (isPrimeLong(num)){
    
63.                 /*
    
64.                  * 判断这个另一个数是否是素数
    
65.                  * 如果是 那么分配一个数据的内存
    
66.                  * 因为数据可能比较大 所以用long long类型储存
    
67.                  * 把这个数放入long long 类型的数组array2里面
    
68.                  */
    
69.                 array2 = (long long *)realloc(array2, sizeof(long long));
    
70.                 array2[cnt] = i;
    
71.                 cnt2++;
    
72.             }
    
73.         }
    
74.     }
    
75. 
    
76.     /*
    
77.      * 分别遍历两个数组
    
78.      */
    
79.     for (int i = 0; i < cnt; ++i) {
    
80.         printf("%d ", array[i]);
    
81.     }
    
82. 
    
83.     for (int i = 0; i < cnt2; ++i) {
    
84.         printf("%lld ", array2[i]);
    
85.     }
    
86. 
    
87.     free(array);    // 释放内存
    
88.     free(array2);
    
89. 
    
90.     return 0;
    
91. }
    

复制代码

永恒的蓝色梦想

cupbbboom 发表于 2018-11-15 16:46
有没有跟我一样：先百度  合数 、质数因子，然后就有了百度  什么是质数？什么是因数？什么是整数、正整数? ...

这是小学的知识

永恒的蓝色梦想

guoquanli 发表于 2019-12-31 14:56
非常感谢您的分享，请教您一下，我在linux环境下运行您的这段代码提示：unknown  type  name '__int64', ...

把 __int64 改成 long long