论坛 › 欧拉计划（Project Euler） › 题目3：找出一个合数的最大质数因子

欧拉计划 发表于 2015-4-20 23:21:44

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

本帖最后由 欧拉计划 于 2017-1-14 17:43 编辑

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 发表于 2015-5-17 19:24:23

>>> 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

翅膀团 发表于 2015-6-29 16:25:45

本帖最后由 翅膀团 于 2015-11-16 14:08 编辑

#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);
}

如果有错误希望指出

无名侠 发表于 2015-7-9 13:12:20

本帖最后由 无名侠 于 2015-7-9 13:18 编辑

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

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

@小甲鱼

def prime (x):
        if x<=1:
                return False
        for j in range(2,x):
                if not(x%j):
                        returnFalse
        return True
def factor(x):
        for j in range(1,x+1):
                if not(x%j):
                        if(prime(j)):
                                print(j)

无名侠 发表于 2015-7-9 13:20:19

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


{:5_92:}你这个算法有些慢。

牡丹花下死做鬼 发表于 2015-7-19 22:04:58

不废话 用支持C99标准的编译器 使用unsigned long long int 即可装下600851475143
#include <stdio.h>
void main()
{
        unsigned long long int n,i;
        printf("\nplease input a number:\n");
        scanf("%llu",&n);
        printf("%llu=",n);
        for(i=2;i<=n;i++)/*从小数除起可以确保该数为质数所以不必判断是否为质数*/
                while(n!=i)/*如果除数不等于被除数就判断能否整除*/
                {
                        if(n%i==0)/*如果可以整除就将除数输出并被除数 = 商*/
                        {
                                printf("%llu*",i);
                                n=n/i;
                        }
                        else
                                break;/*如果除数等于被除数说明已经是最后一个质因数结束循环将其输出*/
                }
                printf("%llu",n);
}

wyc1gg 发表于 2015-10-8 16:32:56

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))
   
=================================
发现自己写的好复杂呀，差距还是很大的和别人的代码！求指教

发表于 2015-10-30 16:07:55

大数用了__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


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


bool IsPrimeNumber(__int64);

int main()
{
        __int64 a = 1; //合数
        __int64 i = 0; //可能的质数因子
        __int64 j = 1; //质数因子序号

        printf("please input a Composite number:");
        scanf ("%l64d",&a);

        for(i = 2;i < a;i ++)
        {
                if(a % i == 0)
                {
                       
                        if(IsPrimeNumber(i) == 1)
                        {
                                printf("the No.%I64d number is %I64d \n",j,i);
                                j ++;
                        }

                }
                       
        }
        return 0;
}

// 判断n是否为质数
bool IsPrimeNumber(__int64 n)
{
    if (n==2)
    {
      return true;
    }

    if (n%2==0)
    {
      return false;
    }

    int sqrtn=(int)sqrt((double)n);
    bool flag=true;

    for (int i=3;i<=sqrtn;i+=2)
    {
      if (n%i==0)
      {
            flag=false;
      }
    }
    return flag;
}

ianv 发表于 2016-3-16 10:57:16

本帖最后由 ianv 于 2016-3-16 11:28 编辑

#include<stdio.h>
#include<stdlib.h>
#include<math.h>
#include<time.h>
int isprime(unsigned long long int num)
{
        unsigned long long int i=2;
        for (i;i<=(int)sqrt((double)num);i++)
        {
                if (num%i==0)
                        return 0;
        }
        return 1;
}
int findmaxprimefactor(unsigned long long int num)
{

        unsigned long long int Maxfactor=(int)sqrt((double)num);
        unsigned long long int lastfactor,factor;
        if (num%2==0)
        {
                lastfactor=2;
                num=num/2;
                while (num%2==0)
                        num=num/2;
        }
        else
                lastfactor=1;
        factor=3;
        while((num>1)&&(factor<Maxfactor))
        {
                if ((num%factor==0)&&(isprime(factor)))
                {
                        /*printf("%u\n",i);*/
                        num/=factor;
                        lastfactor=factor;
                        while(num%factor==0)
                                num/=factor;       
                        Maxfactor=(int)sqrt((double)num);
                }
                factor+=2;
        }
        if (num==1)
                return lastfactor;
        else
                return num;
}

int main()
{
        double start, finish;
        start = clock();//取开始时间
        printf("%d",findmaxprimefactor(600851475143));
        finish = clock();//取结束时间
        printf( "\n%f seconds\n",(finish - start) / CLOCKS_PER_SEC);//以秒为单位显示之
        getchar();
}
0.013s

weilixueba 发表于 2016-4-19 11:02:10

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)

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

张无忌 发表于 2016-5-1 22:39:42

from math import sqrt, floor

def is_prime(num):
    for i in range(2, floor(sqrt(num)) + 1):
      if num%i == 0:
            return False
    return True

def largest_prime_factor(num=600851475143):
    n = floor(sqrt(num))
    while n > 1:
      if is_prime(n) and num%n == 0:
            return n
      n -= 1
    return -1
   
print(largest_prime_factor())

Liu_xy 发表于 2016-5-4 22:23:05

本帖最后由 Liu_xy 于 2016-5-4 22:26 编辑

import math
import time
start = time.clock()
list1 = []
Num = 600851475143
def isPrime(x):
    ret = 0
    for i in range(2, int(math.sqrt(x))):
      if x%i==0:
            ret = 1
    return ret

for i in range(2, int(math.sqrt(Num))):
    if Num % i == 0:
      if isPrime(i) == 0:
            list1.append(i)
      men1 = Num/i
      if isPrime(men1) == 0:
            list1.append(men1)
print(max(list1))
print(list1)
end = time.clock()
print("read:%f s" %(end - start))


6857

read:0.209758 s

飘飞的白杨 发表于 2016-6-10 16:00:45

本帖最后由 飘飞的白杨 于 2016-6-10 16:15 编辑

n = 600851475143*71
i = 2
l = []
while i<=n:
      if n%i==0:
                while n%i==0:
                        n=n//i
                l.append(i)
      i+=1
print(l)
print(l[-1])

huomqh 发表于 2016-6-13 13:30:09

shu=600851475143
zhishu=
x=1
xx=0
while 1:
    x+=2
    z=1
    for i in zhishu:
      if x%i==0: z=0
    if z:
      zhishu.append(x)
    if shu%x==0:
      xx=x
      shu=shu/x
    if x>=shu:
      break

print(xx)

答案6857

冷钟天 发表于 2016-7-4 15:57:31

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

幻世伽蓝 发表于 2016-7-4 16:05:44

def primer(x):
    for n in range(2,x + 1 // 2):
      if x % n == 0:
            return 0
    return x
   

num = 600851475143

for i in range(2,num + 1):
    if primer(i):
      if num % i == 0:
            print(i)

#include <stdio.h>

unsigned long long primer_factor(unsigned long long n)
{
    unsigned long long x;
    for(x = 2; x <= n / 2; x++)
    {
      if(n % x == 0)
      return 0;
    }
    return n;
}
int main()
{
    unsigned long long num = 600851475143;
    unsigned long long i, j;
    for(i = 2; i <= num; i++)
    {
      //printf("0");
      if (j = primer_factor(i))
      {
            if(num % j == 0)
                printf("%u\n",j);
      }
    }
    return 0;
}


71/839/1471/6857   之后就没有反应了{:5_96:}

zhongjiahong 发表于 2016-7-7 17:44:53

#/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 发表于 2016-7-7 17:49:48

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

DAY 发表于 2016-7-11 10:46:41

好吧数据太大，，只能用long long了
#include <iostream>
#include <cmath>

using namespace std;

bool IsPrime(const unsigned long long & data)
{
    unsigned long long i;
    for (i = 2; i <= sqrt(data); i++)
    {
      if (data % i == 0)
      {
            return false;
      }
    }
    return true;
}

unsigned long long MaxFact(const unsigned long long & data)
{
    unsigned long long i;
    for (i = data-1; i > 1; i--)
    {
      if (data % i == 0 && IsPrime(i))
      {
            return i;
      }
    }
    return 1;
}

int main()
{
    unsigned long long n;
    cout<<"输入数据:";
    cin>>n;
    if (n <= 0)
    {
      cout<<"输入必须大于1"<<endl;
      return 1;
    }
    cout<<n<<"的最大质因数为:"<<MaxFact(n)<<endl;
    return 0;
}

期待更好的思路。。。

过河的小卒 发表于 2016-7-18 15:28:57

71
839
1471
6857
import math
def judgePrimes(num):         #剽窃了鱼哥的素数判断算法
    if num%2 == 0:
      return False
    for i in range(3,int(math.sqrt(num))+1,2):
      if not num%i:
            return False
    else:
      return True

def bigPrimeNum(num):          #用了递归的方法
    if judgePrimes(num):
      return num
    for i in range(3,num):
      if num%i == 0:
            print(i)
            return bigPrimeNum(num//i)

if __name__ == '__main__':
    print(bigPrimeNum(600851475143))

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

查看完整版本: 题目3：找出一个合数的最大质数因子