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

发表于 2018-1-16 10:18:42

{:10_256:}

发表于 2018-1-16 10:19:35

/*判断是否是素数*/
public static Boolean prime(long x){
   for(int i=2;i<=Math.sqrt(x);i++){
         if(x%i==0) return false;
   }
   return true;
}
/**
      * test3 查找最大素数因子
      */
   long flag=0;
   long num=600851475143l;
   for(long i=2;i<=Math.sqrt(num);){
         //System.out.println(i);
         if(num%i==0){
            System.out.println(i);
            if(prime(num/i)==true)
            {
               flag=num/i;
               System.out.println("flag"+num/i);
               i+=Math.sqrt(num);
            }else{
               if(prime(i)==true){
                     flag=i;
                     i+=2;
               }
               else
                     i+=2;
            }
         }else
            i+=1;
   }
   if(flag==0)
         System.out.println("最大素数因子为："+num);
   else
         System.out.println("最大素数因子是："+flag);
}

artistlu 发表于 2018-2-8 16:32:14

#include <stdio.h>

int isPrime(long long);

int isPrime(long long num)
{
long long i;
for (i= 2; i <= num / i; i++)
{
   if (num % i == 0)
   {
         break;
   }
}

return i > num / i;
}

int main(void)
{
long long maxPrime;
long longtarget;
scanf("%lld", &target);

if (isPrime(target))
{
   maxPrime = target;
}
else
{
   for (long long i = 2; i <= target / i; i++)
   {
         if (target % i == 0)
         {
            if (isPrime(i))
            {
               maxPrime = i;
            }

            if (isPrime(target / i))
            {
               maxPrime = target / i;
            }
         }
   }

}

printf("%lld\n", maxPrime); //6008514751436857
return 0;
}

由我们主宰 发表于 2018-3-4 15:02:55

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

int CheckPrime(int m)
{
int i,leap=1;
for(i=2;i<=sqrt(m);i++)
{
if(m%i==0)
{
leap=0;
break;
}
}
return leap;
}
int main()
{
int m,n;
printf("请输入一个合数:");
scanf("%d",&n);
for(m=n;m>1;m--)
{
if(n%m==0)
{
if(CheckPrime(m))
{
printf("%d\n",m);
break;
}
}
}
return 0;
}

阿bang 发表于 2018-3-26 16:29:27

def isprime(num):
if num < 2:
   return False
elif num == 2:
   return True
for i in range(3, int(num ** 0.5) + 1, 2):
   if num % i == 0:
         return False
else:
   return True

def maxprimefac(num):
for i in range(int(num ** 0.5), 2, -1):
   if num % i == 0:
         anthornum = num / i
         if isprime(i) and isprime(anthornum):
            return max(i, num / i)
         elif isprime(i):
            return i
         elif isprime(anthornum):
            return anthornum
else:
   return num
print maxprimefac(600851475143)

soulwyb 发表于 2018-4-12 20:00:35

def maxzhisu(n):
s = 0
if n < 4:
   print "这不是合数"
   return False
for i in range(4, n):
   if n % i == 0:
         for w in range(2,i+1):
            if i % w == 0:
               if w in :
                     s = w
            else:
               s = w
if s:
   return "最大质数是%d" % s
else:
   return "这不是一个合数，泥煤"

m = maxzhisu(100)
print m

发表于 2018-4-21 15:45:50

#-*- codding:utf-8 -*-

import math
import time
start = time.clock()
list1 = []
Num = 600851475143

def isPrime(x):

for i in range(2, int(math.sqrt(x))):

if i == int(math.sqrt(x))-1:

list1.append(x)

if x % i == 0:

list1.append(i)
x = x / i

if x >= 1 :

isPrime(x)

break

isPrime(Num)
print(max(list1))
print(list1)

end = time.clock()
print("read:%f s" % (end - start))

yunying12321 发表于 2018-4-28 08:29:35

def isprime(n):
if n == 1:
   return False
elif n == 2:
   return True
elif n > 2:
   for i in range(2, n//2+2):
         if n%i == 0:
            return False
   else:
         return True

def ds(n):

if n == 1 or n == 2:
   yield n
elif n > 2:
   for i in range(2, n//2+2):
         if n%i == 0 and isprime(i):
            yield i
            x = n//i
            while x%i == 0:
               yield i
               x //= i

def main():
n = int(input('输入一个整数：'))
l = []
f = ds(n)

while True:
   try:
         s = next(f)
   except:
         break
   l.append(str(s))

print(n, '=', '*'.join(l))
print('最大的质因子：', l[-1])

if __name__ == '__main__':
while True:
   main()

使用迭代器，奇怪的是，输入600851475143以后，答案一直不出来，我按了ctrl+c停止后，马上就出答案了
不知道是什么环节出问题了

ufo20085 发表于 2018-5-4 01:29:15

import time
import math
from numba import jit

def get_yinzi(x):
listall=
for i in range(2,int(math.sqrt(x)),1):
   if x%i == 0:
         listall.append(i)
listall.append(x)
return listall

i = 600851475143

starttime=time.time()
a=get_yinzi(i)
a.reverse()
for each in a:
if len(get_yinzi(each)) == 2:
   print(each)
   break
endtime=time.time()
print(endtime-starttime)

0.2s
思路：定义一个函数，求数的因子列表。对该数的因子从大到小求因子的因子列表，如果列表长为2，则该数为质数。

ssd8661366 发表于 2018-5-4 22:13:23

本帖最后由 ssd8661366 于 2018-5-5 15:38 编辑

import math

#质数Generator
def Prime():
yield 2
num = 3
while True:
   judge = True
   for i in range(2,int(math.sqrt(num))+1):
         if num%i == 0:
            judge = False
            break
   if judge:
         yield num
   num += 2

#质因子分解
def analysis(num):
num_list =
myP = Prime()
while num != 1:
   prime = next(myP)
   while num%prime == 0:
         num_list.append(prime)
         num /= prime
return num_list

print(analysis(600851475143))

结果：
最大质数：6857
运行时间：0.00500798

li1347zhen 发表于 2018-5-22 17:10:51

#include<stdio.h>
#include<math.h>
int prime(long long intx);
long long int nextprime(longlong int x);
int main()
{
long int x=2;
long long int divisor = x;
long longint dividend = 600851475143;
long long int quotient=0;
while (1) {
if (dividend%divisor == 0) {
printf("%lld\n", divisor);

quotient = dividend / divisor;
if (quotient == 1)
break;
dividend = quotient;
divisor = 2;

}
divisor = nextprime(divisor);
}
//printf("%d\n", prime(y));
return 0;
}
int prime(long long int x)//返回1 表 x为素数
{
longint i = 2;
double y = sqrt(x);
while (i <= y) {
if (x%i == 0)
return 0;
i++;
}
return 1;

}
long long int nextprime(long long int x)
{
while (1) {
x++;
if (prime(x)) {
break;
}
}
return x;
}

zzzgod 发表于 2018-6-20 15:54:23

#include <iostream>
#include <cmath>
#include <algorithm>
#include <vector>

using namespace std;

int main()
{
int max=0;
vector<int> dest;
const long long num=600851475143;
for(int i=2;i<(int)sqrt(num);++i)
{
if(num%i==0 && !distance(find(dest.begin(),dest.end(),i),dest.end()))
{
dest.push_back(i);
}
}
cout<<dest.back();
}

答案：486847

zzzgod 发表于 2018-6-20 16:06:06

zzzgod 发表于 2018-6-20 15:54
#include
#include
#include

#include <iostream>
#include <cmath>
#include <algorithm>
#include <vector>

using namespace std;

bool zhishu(int x)
{
for(int i=2;i<sqrt(x);++i)
{
if(x%i==0)
{
return 0;
}
}
return 1;
}

int main()
{
int max=0;
vector<int> dest;
const long long num=600851475143;
for(int i=2;i<(int)sqrt(num);++i)
{
if(num%i==0 && zhishu(i))
{
dest.push_back(i);
}
}
cout<<dest.back();
}

ThatGirl 发表于 2018-6-30 15:40:26

from math import sqrt
from time import time

# 素数判断函数，给一个值，如果返回True，则表示是素数，False表示为非素数
def is_prime(n):
if n > 1:
   if n == 2:
         return True
   if n % 2 == 0:
         return False
   for i in range(3, int(sqrt(n))+1, 2):
         if n % i == 0:
            return False
   # for循环结束后，如无False，则返回True
   return True
# 如 if n > 1 不成立，则返回False
return False

# 取得给定值的所有乘数因子
def factor(n):
L = []
for i in range(1, int(sqrt(n))+2):
   if n%i == 0:
         L.append(i)
         L.append(n/i)
# set 去除相同的因子
return set(L)

start_time = time()
memb = list(filter((is_prime), factor(600851475143)))
memb.sort()
end_time = time()

print(memb)
print('Running time = ', end_time - start_time)
print('Largest prime factor is ', memb[-1])
>>>

Running time =0.113600015640
Largest prime factor is6857

塔利班 发表于 2018-8-23 16:31:31

def fun(x):
a=[]
while x!=1:
   for i in range(3,int(x**(0.5))+1,2):
         if x%i==0:
            a.append(i)
            x//=i
return max(a)

shanczp 发表于 2018-10-9 20:24:01

输出 71 839 1471 6857,相乘得出的结果正确，中间遇到了一个很麻烦的问题。。就是定义int老是报溢出。。我一直不知道哪个可以，最后用了__int64才成功赋值了
int n=0;
__int64 num=600851475143;
while (true)
{
int i=2;
for(;i<=num;i++)
{
if(num%i==0)
{
n=i;
break;
}
}
printf("%ld\n",n);
num=num/n;
if(num==1)
break;
}

cupbbboom 发表于 2018-11-15 16:46:55

有没有跟我一样：先百度合数、质数因子，然后就有了百度什么是质数？什么是因数？什么是整数、正整数?然后就......崩溃了，不想看下去{:9_219:}

996982937 发表于 2019-2-21 16:39:53

#include<stdio.h>
#include<math.h>
void main()
{
long unsigned int i,a;
int flag=1;
for(i=2;i<=(600851475143/2)&&i>1;i++)
{
if(600851475143%i==0)
{
for(a=2;a<=(long unsigned int)sqrt(i);a++)
{
if(i%a==0)
{
flag=0;
break;
}
}
if(flag==1)
{
printf("%d\n",i);
}
flag=1;
}
}
}

输出结果
71
839
1471
6857

大大大敏 发表于 2019-3-17 15:42:41

#include <stdio.h>
int main()
{
long long i,n;
scanf("%lld",&n);
for(i = 2; i <= n; i ++)/*从小数除起可以确保该数为质数所以不必判断是否为质数*/
{
while(n != i)
   {
         if(n % i == 0)
            n = n / i;
         else
            break;
   }
}
printf("%lld",n);
}

ietar 发表于 2019-4-17 21:38:59

python 6857

def p3():
import math
a = 600851475143
def is_prime(n):
   if not n%2:
         return False
   n1 = int(math.sqrt(n))
   for i in range(3,n1+1,2):
         if not n%i:
            return False
   return True
# 肉眼可见2不是a的约数
def p3_1(n):
   if is_prime(n):
         return n
   for i in range(3,a//3+1):
         if not n%i:
            return p3_1(n/i)
print(p3_1(a))

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

鱼C论坛's Archiver