题目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
输出上面内容后就很久没有再次输出了  先挂一天吧。

@小甲鱼

def prime (x):
        if x<=1:
                return False
        for j in range(2,x):
                if not(x%j):
                        return  False
        return True
def factor(x):
        for j in range(1,x+1):
                if not(x%j):
                        if(prime(j)):
                                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

#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

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

#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

#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

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)

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

张无忌

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

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
[71, 839, 1471, 6857]
read:0.209758 s

飘飞的白杨

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

shu=600851475143
zhishu=[2]
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

冷钟天

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

幻世伽蓝

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   之后就没有反应了

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

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

好吧数据太大，，只能用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;
}

期待更好的思路。。。

过河的小卒

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

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