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

欧拉计划

Largest prime factor

The prime factors of 13195 are 5, 7, 13 and 29.

What is the largest prime factor of the number 600851475143 ?

题目：

13195 的质数因子有 5, 7, 13 和 29。

600851475143 的最大质数因子是多少？

Mikel

>>> def pr(i):
        for x in range(2,i//2):
                if i % x == 0:
                        return False
        else :
                return True


>>> def pf(x):
        i=x//2
        while i:
                if (x % i == 0):
                        if pr(i):
                                return i
                i -= 1

翅膀团

#include <stdio.h>

int main(void)
{
    int i,j,max=0,temp;
   
  for(i=2;i<600851475143;i++)
    {
        if(600851475143 % i == 0)
        {
            for(j=2;j<i;j++)
            {
            if(i % j ==0)
            {
                goto z;
            }
            }
            max = i;
z:         temp = 0;
        }
    }
    printf("%d\n",max);
}

如果有错误希望指出

无名侠

求大神优化。。
factor(600851475143)  跑了几分钟了，。。。。。:huffy:

71
839
1471
6857
输出上面内容后就很久没有再次输出了  先挂一天吧。

@小甲鱼

1. def prime (x):
   
2.         if x<=1:
   
3.                 return False
   
4.         for j in range(2,x):
   
5.                 if not(x%j):
   
6.                         return  False
   
7.         return True
   
8. def factor(x):
   
9.         for j in range(1,x+1):
   
10.                 if not(x%j):
    
11.                         if(prime(j)):
    
12.                                 print(j)

复制代码

无名侠

Mikel 发表于 2015-5-17 19:24
>>> def pr(i):
        for x in range(2,i//2):
                if i % x == 0:

你这个算法有些慢。

牡丹花下死做鬼

不废话 用支持C99标准的编译器 使用unsigned long long int 即可装下600851475143

1. #include <stdio.h>
   
2. void main()
   
3. {
   
4.         unsigned long long int n,i;
   
5.         printf("\nplease input a number:\n");
   
6.         scanf("%llu",&n);
   
7.         printf("%llu=",n);
   
8.         for(i=2;i<=n;i++)/*从小数除起可以确保该数为质数所以不必判断是否为质数*/
   
9.                 while(n!=i)/*如果除数不等于被除数就判断能否整除*/
   
10.                 {
    
11.                         if(n%i==0)/*如果可以整除就将除数输出并被除数 = 商*/
    
12.                         {
    
13.                                 printf("%llu*",i);
    
14.                                 n=n/i;
    
15.                         }
    
16.                         else
    
17.                                 break;/*如果除数等于被除数说明已经是最后一个质因数结束循环将其输出*/
    
18.                 }
    
19.                 printf("%llu",n);
    
20. }

复制代码

wyc1gg

def prime(x):
    is_prime = 1
   
    if x == 1:
     #   print('%d不是质数'%x)
        is_prime = 0
    else:
        for i in range(2,x):
            if x % i ==0:
                is_prime = 0
                break
    #    if is_prime == 1 :
    #        print('%d是质数'%x)
    #    else:
    #        print('%d不是质数'%x)
    return is_prime

def list_prime(x):
    s=[]

    for i in range(1,x+1):
        if prime(i) == 1:
            s.append(i)
    #print('%d'%x + '前的质数序列：%s'%str(s))
    return s
        


def last_prime(x):

    if prime(x) == 1:
        print('%d'%x+'的最大质数因子为：%d'%x)
    else:
        s1 = []

        for i in list_prime(x):
            if x % i == 0:
                s1.append(i)
        print('%d'%x + '的质数因子是：%s'%str(s1))
               
        print('%d'%x + '的最大质数因子是：%d'%(s1[len(s1)-1]))
   
=================================
发现自己写的好复杂呀，差距还是很大的和别人的代码！求指教

大数用了__int64类型

输出结果：
please input a Composite number:600851475143
the No.1 number is 7
the No.2 number is 17
the No.3 number is 47
the No.4 number is 688543

1. #include <stdio.h>
   
2. #include <math.h>
   
3. 
   
4. 
   
5. bool IsPrimeNumber(__int64);
   
6. 
   
7. int main()
   
8. {
   
9.         __int64 a = 1; //合数
   
10.         __int64 i = 0; //可能的质数因子
    
11.         __int64 j = 1; //质数因子序号
    
12. 
    
13.         printf("please input a Composite number:");
    
14.         scanf ("%l64d",&a);
    
15. 
    
16.         for(i = 2;i < a;i ++)
    
17.         {
    
18.                 if(a % i == 0)
    
19.                 {
    
20.                        
    
21.                         if(IsPrimeNumber(i) == 1)
    
22.                         {
    
23.                                 printf("the No.%I64d number is %I64d \n",j,i);
    
24.                                 j ++;
    
25.                         }
    
26. 
    
27.                 }
    
28.                        
    
29.         }
    
30.         return 0;
    
31. }
    
32. 
    
33. // 判断n是否为质数
    
34. bool IsPrimeNumber(__int64 n)
    
35. {
    
36.     if (n==2)
    
37.     {
    
38.         return true;
    
39.     }
    
40. 
    
41.     if (n%2==0)
    
42.     {
    
43.         return false;
    
44.     }
    
45. 
    
46.     int sqrtn=(int)sqrt((double)n);
    
47.     bool flag=true;
    
48. 
    
49.     for (int i=3;i<=sqrtn;i+=2)
    
50.     {
    
51.         if (n%i==0)
    
52.         {
    
53.             flag=false;
    
54.         }
    
55.     }
    
56.     return flag;
    
57. }

复制代码

ianv

1. #include<stdio.h>
   
2. #include<stdlib.h>
   
3. #include<math.h>
   
4. #include<time.h>
   
5. int isprime(unsigned long long int num)
   
6. {
   
7.         unsigned long long int i=2;
   
8.         for (i;i<=(int)sqrt((double)num);i++)
   
9.         {
   
10.                 if (num%i==0)
    
11.                         return 0;
    
12.         }
    
13.         return 1;
    
14. }
    
15. int findmaxprimefactor(unsigned long long int num)
    
16. {
    
17. 
    
18.         unsigned long long int Maxfactor=(int)sqrt((double)num);
    
19.         unsigned long long int lastfactor,factor;
    
20.         if (num%2==0)
    
21.         {
    
22.                 lastfactor=2;
    
23.                 num=num/2;
    
24.                 while (num%2==0)
    
25.                         num=num/2;
    
26.         }
    
27.         else
    
28.                 lastfactor=1;
    
29.         factor=3;
    
30.         while((num>1)&&(factor<Maxfactor))
    
31.         {
    
32.                 if ((num%factor==0)&&(isprime(factor)))
    
33.                 {
    
34.                         /*printf("%u\n",i);*/
    
35.                         num/=factor;
    
36.                         lastfactor=factor;
    
37.                         while(num%factor==0)
    
38.                                 num/=factor;       
    
39.                         Maxfactor=(int)sqrt((double)num);
    
40.                 }
    
41.                 factor+=2;
    
42.         }
    
43.         if (num==1)
    
44.                 return lastfactor;
    
45.         else
    
46.                 return num;
    
47. }
    
48. 
    
49. int main()
    
50. {
    
51.         double start, finish;
    
52.         start = clock();//取开始时间
    
53.         printf("%d",findmaxprimefactor(600851475143));
    
54.         finish = clock();//取结束时间
    
55.         printf( "\n%f seconds\n",(finish - start) / CLOCKS_PER_SEC);//以秒为单位显示之
    
56.         getchar();
    
57. }

复制代码

0.013s

weilixueba

import math as m
def isprime(n):
    if n <= 1:
        return 0
    i=2
    while i * i <= n:
        if n % i == 0:
            return 0
        i += 1
    return 1

a = int(input('please enter a number'))
b =int(m.sqrt(a))
while b > 0:
    s = isprime(b)
    if (a % b ==0) and (s == 1):
        break
    b -=1


print(b)

将近一分钟，有没有好的算法
从小的开始

张无忌

1. from math import sqrt, floor
   
2. 
   
3. def is_prime(num):
   
4.     for i in range(2, floor(sqrt(num)) + 1):
   
5.         if num%i == 0:
   
6.             return False
   
7.     return True
   
8. 
   
9. def largest_prime_factor(num=600851475143):
   
10.     n = floor(sqrt(num))
    
11.     while n > 1:
    
12.         if is_prime(n) and num%n == 0:
    
13.             return n
    
14.         n -= 1
    
15.     return -1
    
16.    
    
17. print(largest_prime_factor())

复制代码

Liu_xy

1. import math
   
2. import time
   
3. start = time.clock()
   
4. list1 = []
   
5. Num = 600851475143
   
6. def isPrime(x):
   
7.     ret = 0
   
8.     for i in range(2, int(math.sqrt(x))):
   
9.         if x%i==0:
   
10.             ret = 1
    
11.     return ret
    
12. 
    
13. for i in range(2, int(math.sqrt(Num))):
    
14.     if Num % i == 0:
    
15.         if isPrime(i) == 0:
    
16.             list1.append(i)
    
17.         men1 = Num/i
    
18.         if isPrime(men1) == 0:
    
19.             list1.append(men1)
    
20. print(max(list1))
    
21. print(list1)
    
22. end = time.clock()
    
23. print("read:%f s" %(end - start))

复制代码

6857
[71, 839, 1471, 6857]
read:0.209758 s

飘飞的白杨

1. n = 600851475143*71
   
2. i = 2
   
3. l = []
   
4. while i<=n:
   
5.         if n%i==0:
   
6.                 while n%i==0:
   
7.                         n=n//i
   
8.                 l.append(i)
   
9.         i+=1
   
10. print(l)
    
11. print(l[-1])

复制代码

huomqh

1. shu=600851475143
   
2. zhishu=[2]
   
3. x=1
   
4. xx=0
   
5. while 1:
   
6.     x+=2
   
7.     z=1
   
8.     for i in zhishu:
   
9.         if x%i==0: z=0
   
10.     if z:
    
11.         zhishu.append(x)
    
12.     if shu%x==0:
    
13.         xx=x
    
14.         shu=shu/x
    
15.     if x>=shu:
    
16.         break
    
17. 
    
18. print(xx)
    

复制代码

答案6857

冷钟天

n=600851475143
a=2
while n!=a:
        if n%a==0:
                n=int(n/a)
        a+=1
        if n==a:
                print('最大质数是',a)

幻世伽蓝

1. def primer(x):
   
2.     for n in range(2,x + 1 // 2):
   
3.         if x % n == 0:
   
4.             return 0
   
5.     return x
   
6.    
   
7. 
   
8. num = 600851475143
   
9. 
   
10. for i in range(2,num + 1):
    
11.     if primer(i):
    
12.         if num % i == 0:
    
13.             print(i)

复制代码

1. #include <stdio.h>
   
2. 
   
3. unsigned long long primer_factor(unsigned long long n)
   
4. {
   
5.     unsigned long long x;
   
6.     for(x = 2; x <= n / 2; x++)
   
7.     {
   
8.         if(n % x == 0)
   
9.         return 0;
   
10.     }
    
11.     return n;
    
12. }
    
13. int main()
    
14. {
    
15.     unsigned long long num = 600851475143;
    
16.     unsigned long long i, j;
    
17.     for(i = 2; i <= num; i++)
    
18.     {
    
19.         //printf("0");
    
20.         if (j = primer_factor(i))
    
21.         {
    
22.             if(num % j == 0)
    
23.                 printf("%u\n",j);
    
24.         }
    
25.     }
    
26.     return 0;
    
27. }
    

复制代码

71/839/1471/6857   之后就没有反应了

zhongjiahong

#/usr/bin/env python
#coding:utf-8
'''
13195的质数因子有5,7,13和29.

600851475143的最大质数因子是多少？

'''
num=600851475143

def isPrime(number):
    '''判断一个数是不是质数，如果是返回真，否则返回假'''
    if number<2:
        return False
    if number == 2:
        return True
    for i in range(2,int(number**0.5)+1):
        if number%i==0:
            return False
    return True

def largestPrimeFactor(num):

    for m in range(int(num**0.5),0,-1):
        if num%m==0:
            if isPrime(m):
                return m
    return None


m=largestPrimeFactor(num)
print(m)

zhongjiahong

1. #/usr/bin/env python
   
2. #coding:utf-8
   
3. '''
   
4. 13195的质数因子有5,7,13和29.
   
5. 
   
6. 600851475143的最大质数因子是多少？
   
7. 
   
8. '''
   
9. num=600851475143
   
10. 
    
11. def isPrime(number):
    
12.     '''判断一个数是不是质数，如果是返回真，否则返回假'''
    
13.     if number<2:
    
14.         return False
    
15.     if number == 2:
    
16.         return True
    
17.     for i in range(2,int(number**0.5)+1):
    
18.         if number%i==0:
    
19.             return False
    
20.     return True
    
21. 
    
22. def largestPrimeFactor(num):
    
23. 
    
24.     for m in range(int(num**0.5),0,-1):
    
25.         if num%m==0:
    
26.             if isPrime(m):
    
27.                 return m
    
28.     return None
    
29. 
    
30. 
    
31. m=largestPrimeFactor(num)
    
32. print(m)

复制代码

1秒钟就出结果  还发现一个规律如果如果一个数没有质因数，那么它本身肯定是一个质数
正如算数基本定理：每一个合数都可以以唯一形式被写成质数的乘积，即分解质因数。

DAY

好吧数据太大，，只能用long long了

1. #include <iostream>
   
2. #include <cmath>
   
3. 
   
4. using namespace std;
   
5. 
   
6. bool IsPrime(const unsigned long long & data)
   
7. {
   
8.     unsigned long long i;
   
9.     for (i = 2; i <= sqrt(data); i++)
   
10.     {
    
11.         if (data % i == 0)
    
12.         {
    
13.             return false;
    
14.         }
    
15.     }
    
16.     return true;
    
17. }
    
18. 
    
19. unsigned long long MaxFact(const unsigned long long & data)
    
20. {
    
21.     unsigned long long i;
    
22.     for (i = data-1; i > 1; i--)
    
23.     {
    
24.         if (data % i == 0 && IsPrime(i))
    
25.         {
    
26.             return i;
    
27.         }
    
28.     }
    
29.     return 1;
    
30. }
    
31. 
    
32. int main()
    
33. {
    
34.     unsigned long long n;
    
35.     cout<<"输入数据:";
    
36.     cin>>n;
    
37.     if (n <= 0)
    
38.     {
    
39.         cout<<"输入必须大于1"<<endl;
    
40.         return 1;
    
41.     }
    
42.     cout<<n<<"的最大质因数为:"<<MaxFact(n)<<endl;
    
43.     return 0;
    
44. }

复制代码

期待更好的思路。。。

过河的小卒

71
839
1471
6857

1. import math
   
2. def judgePrimes(num):         #剽窃了鱼哥的素数判断算法
   
3.     if num%2 == 0:
   
4.         return False
   
5.     for i in range(3,int(math.sqrt(num))+1,2):
   
6.         if not num%i:
   
7.             return False
   
8.     else:
   
9.         return True
   
10. 
    
11. def bigPrimeNum(num):          #用了递归的方法
    
12.     if judgePrimes(num):
    
13.         return num
    
14.     for i in range(3,num):
    
15.         if num%i == 0:
    
16.             print(i)
    
17.             return bigPrimeNum(num//i)
    
18. 
    
19. if __name__ == '__main__':
    
20.     print(bigPrimeNum(600851475143))

复制代码

算法效率不错，几秒钟出结果