题目3：找出一个合数的最大质数因子,欧拉计划（Project Euler）,数据结构与算法,鱼C论坛

0mrli0 发表于 2017-2-20 07:00:43

本帖最后由 0mrli0 于 2017-2-20 07:02 编辑

/*找一个合数的最大质数因子
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 发表于 2017-2-20 21:12:25

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

returnzhiyinzi

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

6leensky 发表于 2017-2-25 15:34:38

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 发表于 2017-2-27 11:16:19

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

余欲渔 发表于 2017-3-1 16:05:45

不严谨的解法
zhishu=
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

夜魔时生 发表于 2017-3-6 11:26:16

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

99592938 发表于 2017-3-14 11:54:35

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

read:0.209758 s

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

翼-- 发表于 2017-3-20 17:13:31

#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 发表于 2017-3-26 16:40:54

#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 发表于 2017-3-26 16:42:11

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 发表于 2017-4-16 02:03:19

本帖最后由 Eagle.Tong 于 2017-4-16 02:12 编辑

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

天之南 发表于 2017-4-30 18:58:06

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

铭记太阳 发表于 2017-5-4 13:15:57

答案是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;
}

俞晨曦 发表于 2017-6-20 23:43:15

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

水冢发表于 2017-8-21 23:06:02

#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 发表于 2017-9-8 15:02:38

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 发表于 2017-9-10 10:31:38

#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 发表于 2017-9-29 16:02:54

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 发表于 2018-1-4 11:57:05

本帖最后由 zjhnz 于 2018-1-4 11:59 编辑

错了

zjhnz 发表于 2018-1-4 12:53:53

答案 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;
}

页: 1 2 [3] 4 5 6 7 8

鱼C论坛's Archiver