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

0mrli0

/*找一个合数的最大质数因子
600851475143的最大质数因子是多少？
分析：先分解质因式，再输出最大结果。*/

#include <stdio.h>
#define N 600851475143

int main()
{
    unsigned long long i, maxfactor;
    unsigned long long n = N;
    for(i=2; i<=n; i++)  
    {
        while(n%i == 0)
        {
            printf("%u ", i);
            n = n / i;
            maxfactor = n==1 ? maxfactor : n;
        }
    }
    printf("\nmaxfactor = %u\n",maxfactor);
    return 0;
}

71 839 1471 6857
maxfactor = 6857

Process returned 0 (0x0)   execution time : 0.014 s

marmot

print("""问题： 13195 的质数因子有 5, 7, 13 和 29。
600851475143 的最大质数因子是多少？
-------------------------------------------------""")

# 数字除以2，若能被整除，取结果继续除以 i = 2，若不能则除以 i+1：
# 依序递增，直到被自己除，此时的数字即为所求的最大质因子。

def zhiyinzi(x):
    i=2
    while x != 1 :              # x 不等于 1
        if x % i == 0:           # 能除尽2
            x = x/i               # 继续除
            zhiyinzi = i           # 得到最大质因子
        else:
            i += 1                  # 除不尽就 +1

    return  zhiyinzi

print("答案是： " + str(zhiyinzi(600851475143)))

6leensky

n = 600851475143
i = 2
while i <= n/2:     # 最大的质因数不大于被2除后的商
    while n%i == 0: #能被i除尽
        n = n/i     #能被i除尽，将商赋予n，继续除，直至除尽重复的约数
    i += 1          #若除不尽，i＋1，外侧循环
print(n)            #直至最后，约数是其本身，则为质因数，且最大

我的答案是 6857
也有其他鱼油推荐了，能够可视化python程序执行的网站，再推荐之   http://www.pythontutor.com/

pan1990

def pm(n):
    if n==1:
        return 1
    else:
          for i in range(1,((n//2)+1)):
              if n%i ==0:
                  #print(i)
                  n=n//i
                  return (pm(n))
          else:
                return n

余欲渔

不严谨的解法

zhishu=[2,3]
def jc(i):
    for x in zhishu:
        if i%x==0:return 1
for i in range(5,10000,2):
    if jc(i):continue
    if i not in zhishu:zhishu.append(i)
zhishu.reverse()
for i in zhishu:
    if 600851475143%i==0:
        print(i)
        break

>>> 
== RESTART: C:\Users\ASUS\AppData\Local\Programs\Python\Python35-32\test.py ==
6857

夜魔时生

l=[]
a=600851475143
for i in range(2,a//2):
    if a%i==0:
        l.append(i)
print(max(l))
    

99592938

Liu_xy 发表于 2016-5-4 22:23
6857
[71, 839, 1471, 6857]
read:0.209758 s

int(math.sqrt(x)要+1，不然你试试13195？

翼--

#include <stdio.h>
#include <stdlib.h>

int main()
{
long long num = 0;
printf("***input the number:\n");
scanf("%lld",&num);
long long flag = 0;       //存放最大质因数

//对于偶合数先进行转换成奇数操作
while(num % 2 == 0)
{
num = num / 2;
flag = 2;
}

//对于奇合数进行操作，模上从3开始的奇数
while(1)
{
if(num % i == 0)
{
//对于合数中的因数进行质数判断，是质数的存放到flag中
long long j = 2;
for(; j <= i / 2; j++){
if(i % j == 0)
break;
}
if(j > i / 2){
flag = i;
num = num / i;
}
}
if(num < i)
break;
i = i + 2;
}
printf("***the largest prime factor is %lld",flag);
}

JonTargaryen

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

int main(void)
{
    long int number;
    int factor;

    // number = 13195;
    number = 600851475143;

    for(factor = 2; factor <= sqrt(number); factor++)
    {
        if(!(number % factor))
        {
            number /= factor;
            printf("%d ", factor);
        }
    }
    printf("\n");

    printf("%ld\n", number);

    return 0;
}

JonTargaryen

import math

# number = 13195
number = 600851475143

factor = 2
largest = int(math.sqrt(number))

while factor <= largest:
    if not (number % factor):
        number /= factor
        print(factor, end = ' ')

        factor = 1
        largest = int(math.sqrt(number))

    factor += 1

print("\nThe largest prime factor is:", int(number))

Eagle.Tong

Python
#求600851475143的最大质数因子

import math
import time


def ifprime(n):
        r = int(math.sqrt(n))
        for i in range(2,r+1):
            if n%i == 0:
                return 0
        return 1

start = time.time()
number = 600851475143
dividend = int(math.sqrt(number)) + 1
Flag = 0
while dividend > 1:
    if number%dividend == 0:
        Flag = ifprime(dividend)
        if Flag == 1:
            print(dividend)
            break
    dividend -= 1

end = time.time()
print(end-start)

6857
0.4s

天之南

#include<stdio.h>

int main(void)
{
        long long x = 600851475143;
        long long maxF = x;
        for (int i = 2; i * i < maxF; i++)
        {
                while (maxF%i == 0) {
                        maxF /= i;
                }
        }
        printf("%ld\n", maxF);

        return 0;
}

铭记太阳

答案是688543

我的代码非常简单，借助比较好的思路；将Num从2到Num/2往下除，如果能除2就循环除2直到除不动为止，同时Num借此机会可以迅速缩小，缩小的结果不但计算变快，同时2到Num/2的范围也在急速缩小，把小因数都除完最后剩下的大块就是最大的因数了。

#include<stdio.h> 

int main(void)
{
        int i;
        unsigned long Num=600851475143;
        for(i=2;i<(Num/2);++i)
        {
                if(Num%i==0)
                {
                        while(Num%i==0)        Num=Num/i;
                }
        }
        printf("%d\n",Num);
        return 0;
}

俞晨曦

bool IsPrime(int num)
{
        int count = (int)sqrt(num);
        int flag = 0;

        for (int i = 2;i <= count && !flag;++i)
        {
                if(num % i == 0)
                        flag = 1;
        }
        if(flag)
                return false;
        else
                return true;
}

int three(int num)
{
        int fact = 1;

        for(int i = 2;i <= num - 1;++i)
        {
                if(num % i == 0 && i > fact && IsPrime(i))
                        fact = i;
        }
        return fact;
}

水冢

#include <stdio.h>

int main(void){
        
        int prime, i;
        long long int n = 600851475143;
        for (i = 2; i < n; i++){
                if (n / i == 0){
                        break;
                }else if (n % i == 0){
                        n = n / i;
                }
        }
        
        printf("answer = %d", i);
        return 0;
}

BngThea

def checkprime(target):
    for i in range(2,int(target/2 + 1)):
        if not(target % i):
            return False
        elif i > int(target/2 - 1):
            return True
        
def maxprime(tar):
    fact = int(tar/2 + 1)
    while fact > 2:
        if not(tar % fact):
            if checkprime(fact):
                break
        fact -= 1
    print(str(tar)+'的最大质数因子是：' + str(fact))
#maxprime(5555)   
maxprime(600851475143)

Kotori

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

long long isPrime(long long num);

int main(void)
{
        long long i;
        long long target = 600851475143;
       
        for (i=3;i<target;i+=2)
        {
                if (target % i == 0)
                {
                        if((isPrime(target / i)) == 1)
                        {
                                printf("%lld的最大质数因子：%lld",target, target / i);
                                break;
                        }
                }
        }
        return 0;
}

long long isPrime(long long num)
{
        long long i;
        long long temp = (long long) sqrt(num);
       
        for(i=3;i<=temp;i+=2)
        {
                if (num % i == 0)
                {
                        return 0;
                }
        }
       
        return 1;
}

jerryxjr1220

AArdio编译：

import console;
import time.timer
 
console.setTitle("test");

time.timer.start();

var n = 600851475143;
var max_p = 0
while (n != 1){
        for(i=2;n;1){
                if(n%i==0){
                        max_p = math.max(max_p,i );
                        n/=i;
                        break;        
                }
        }
}
console.print(max_p);

console.print(time.timer.endTick())
 
console.pause();

6857
0.42870622873306 （单位是毫秒）
请按任意键继续 ...

zjhnz

错了

zjhnz

答案 6857  用时 0.2595秒
#include <stdio.h>
#include <math.h>

int isPrime(unsigned long long n);

int isPrime(unsigned long long n)
{
        unsigned long long temp=sqrt(n);
       
        for ( unsigned long long i=2; i<=temp; i++ )
        {
                if ( n%i ==0)
                {
                        return 0;
                }
               
        }
        return 1;
}

int main(void)
{
        unsigned long long n=600851475143;
        unsigned long long max,i;
       
   while(1)
   {
          
           for (i=3; i<=n; i=i+2)
       
        {       
                if( (n%i)==0 &&isPrime(i) )
                {
                        //printf(" %ld  ",i);
                    n=n/i;
                    break;
                }               
        }       
        if(n==1)
        {
                max=i;
                break;
        }         
                          
          
   }       
        printf("%ld",max);
       
        return 0;
}