编写一个程序，求解 600851475143 的最大质数因子是多少

ksksasd

#include <stdio.h>
int main()
{
       long long a;int flag=0;
       for(a=600851475142;a<600851475143;a--) //最大质数就是取余为0
       {
               if(600851475143%a==0)
               {
                       printf("%lld",a);
                       flag=1;
            }
                if(flag)     //找到了最大质数，flag就=1
                  break;    //跳出for循环
           }
          
        return 0;
}

wp231957

这样做  ，首先你找不到最大质数，另外，就是循环次数太多了  

s=600851475143
a=[]
def iss(n):
    if n==1:return 0
    for x in range(2,n):
        if n%x==0:
            return 0
    return 1            

for x in range(1,10001):
    if iss(x):a.append(x)

print(s,"=",end="")
for y in a:
    if s%y==0:
        s//=y
        if s==1:
            print(y)
        else:
            print(y,"*",end="")     
'''
PS C:\Users\Administrator> & C:/Programs/Python/python.exe d:/wp/test7.py
600851475143 =71 *839 *1471 *6857
'''

wp231957

探测该数的所有因数：

s=s1=600851475143
a=[]
def iss(n):
    if n==1:return 0
    for x in range(2,n):
        if n%x==0:
            return 0
    return 1            

for x in range(1,10001):
    if iss(x):a.append(x)

b=[]
for y in a:
    if s%y==0:
        s//=y
        b.append(y)

import itertools
m=[]
for x in range(1,len(b)+1):
    m.extend(list(itertools.combinations(b,x)))
xh=1
print("%2d: %12d = %d * %d"%(xh,s1,1,s1))
for x in m:
    t=1
    for y in x:
        t*=y
    xh+=1    
    print("%2d: %12d = %d * %d"%(xh,s1,t,s1//t))

'''
PS C:\Users\Administrator> & C:/Programs/Python/python.exe d:/wp/test7.py
 1: 600851475143 = 1 * 600851475143
 2: 600851475143 = 71 * 8462696833
 3: 600851475143 = 839 * 716151937
 4: 600851475143 = 1471 * 408464633
 5: 600851475143 = 6857 * 87625999
 6: 600851475143 = 59569 * 10086647
 7: 600851475143 = 104441 * 5753023
 8: 600851475143 = 486847 * 1234169
 9: 600851475143 = 1234169 * 486847
10: 600851475143 = 5753023 * 104441
11: 600851475143 = 10086647 * 59569
12: 600851475143 = 87625999 * 6857
13: 600851475143 = 408464633 * 1471
14: 600851475143 = 716151937 * 839
15: 600851475143 = 8462696833 * 71
16: 600851475143 = 600851475143 * 1
PS C:\Users\Administrator>
'''    

傻眼貓咪

答案是 6857 吗？

#include <stdio.h>

int isPrime(long long n) {
    if (n == 2 || n == 3) return 1;
    for (long long i = 2; i * i < n; i++) if (!(n % i)) return 0;
    return 1;
}

long long largestPrimeFactor(long long n) {
    long long prime = 2;
    while (n > 1) {
        while (n % prime == 0) n /= prime;
        if (n == 1) break;
        do {
            prime++;
        } while (!isPrime(prime));
    }
    return prime;
}

int main()
{
    printf("%lld", largestPrimeFactor(600851475143));
    return 0;
}

6857

我的思路：
因为 600851475143 数字太大，不可能从 1 至 600851475143 测试是否为它的因数、质数两个测试，这样时间复杂度是不允许的。反方向思考，逐个找出小于 600851475143 的质数，然后再判断是否能除整，便是答案了

傻眼貓咪

Python

from math import sqrt
def isPrime(n):
    if(n in (2, 3)): return True
    for i in range(2, int(sqrt(n))):
        if not n%i: return False
    return True

def largestPrimeFactor(n):
    prime = 2
    while n > 1:
        while not n%prime: n /= prime
        if n == 1: break
        prime += 1
        while not isPrime(prime):
            prime += 1
    return prime

print(largestPrimeFactor(600851475143))

ksksasd

wp231957 发表于 2022-1-30 09:08
这样做  ，首先你找不到最大质数，另外，就是循环次数太多了

不好意思我才刚学c语言；你的是python吗；
我想问下为什么我的思路错了。比如36的最大质数不是18吗，取余为0吗？

ksksasd

ksksasd 发表于 2022-1-30 12:59
不好意思我才刚学c语言；你的是python吗；
我想问下为什么我的思路错了。比如36的最大质数不是18吗，取 ...

就比如我把600851475143改成小一点的数就能计算出正确结果了

ksksasd

ksksasd 发表于 2022-1-30 13:10
就比如我把600851475143改成小一点的数就能计算出正确结果了

我理解了这样不能算出质数因子；
我搞错定义了；
但为什么我的返回值是空白？
不应该打印最大除数吗？

wp231957

ksksasd 发表于 2022-1-30 12:59
不好意思我才刚学c语言；你的是python吗；
我想问下为什么我的思路错了。比如36的最大质数不是18吗，取 ...

18是质数吗，36的最大质因数就是3

ksksasd

wp231957 发表于 2022-1-30 13:23
18是质数吗，36的最大质因数就是3

谢谢你的回复！我搞错了质数定义了。
我的原代码中求的最大整除除数。返回值为空白。这个问题能帮我解决吗？

ksksasd

ksksasd 发表于 2022-1-30 14:51
谢谢你的回复！我搞错了质数定义了。
我的原代码中求的最大整除除数。返回值为空白。这个问题能帮我解决 ...

但我把数字改小，就能得出正确答案。
long long 定义也应该没问题的。

jhq999

int main()
{
        unsigned long long val=0,yinzi=2,s=1;
        printf("输入一个数字:");
        scanf_s("%llu",&val);

        getchar();
        for (int i = yinzi; i < val/yinzi ;i++)//任何一个数都可以分解成全部质数因子的积
        {
                while(val%yinzi)//最小的因子一定是质数因子，最大的因子对应的一定是最小因子
                {
                        yinzi++;
                }
                s*=yinzi;
                printf("%llu×",yinzi);
                val/=yinzi;
                while(!(val%yinzi))
                {
                    val/=yinzi;
                        s*=yinzi;
                        printf("%llu×",yinzi);
                }
        }

        if(val>1)s*=val,printf("%llu=%llu",val,s);//质数因子的积
        else 
                printf("=%llu",s);
        printf("最大质数因子：%llu",val>yinzi?val:yinzi);
        return 0;
}

例如：98
2×49=2×7×7=98

YSW9527

ksksasd 发表于 2022-1-30 14:52
但我把数字改小，就能得出正确答案。
long long 定义也应该没问题的。

数字太大了，计算机得跑一段时间

malloy_123

int func2(long long num){
        long long i=2;
        while(i!=num){
                if(num%i==0)
                        num=num/i;
                else{
                        i++;
                }
        }
        return num;
}

大概就是依次拆解掉最小的因子，最后得到的质数商就是要求的最大质数因子