ksksasd 发表于 2022-1-29 23:51:46

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

#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 发表于 2022-1-30 09:08:37

这样做，首先你找不到最大质数，另外，就是循环次数太多了
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 发表于 2022-1-30 10:17:48

探测该数的所有因数：
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>
'''   

傻眼貓咪 发表于 2022-1-30 11:57:42

本帖最后由 傻眼貓咪 于 2022-1-30 12:01 编辑

答案是 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 的质数，然后再判断是否能除整，便是答案了

傻眼貓咪 发表于 2022-1-30 12:11:50

Pythonfrom 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 发表于 2022-1-30 12:59:26

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

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

ksksasd 发表于 2022-1-30 13:10:37

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

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

ksksasd 发表于 2022-1-30 13:22:47

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

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

wp231957 发表于 2022-1-30 13:23:20

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

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

ksksasd 发表于 2022-1-30 14:51:43

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

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

ksksasd 发表于 2022-1-30 14:52:55

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

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

jhq999 发表于 2022-1-30 18:39:22

本帖最后由 jhq999 于 2022-1-30 18:41 编辑

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 发表于 2022-1-30 22:47:27

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

数字太大了，计算机得跑一段时间
{:10_277:}

malloy_123 发表于 2022-4-28 22:41:24

int func2(long long num){
        long long i=2;
        while(i!=num){
                if(num%i==0)
                        num=num/i;
                else{
                        i++;
                }
        }
        return num;
}
大概就是依次拆解掉最小的因子，最后得到的质数商就是要求的最大质数因子
页: [1]
查看完整版本: 编写一个程序，求解 600851475143 的最大质数因子是多少