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

/*判断是否是素数*/
    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

#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 long  target;
    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); //600851475143  6857
    return 0;
}

由我们主宰

#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

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

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 [2,3]:
                        s = w
                else:
                    s = w
    if s:
        return "最大质数是%d" % s
    else:
        return "这不是一个合数，泥煤"
   
m = maxzhisu(100)
print m

                    

#-*- 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

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

import time
import math
from numba import jit

def get_yinzi(x):
    listall= [1]
    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

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 = [1]
    myP = Prime()
    while num != 1:
        prime = next(myP)
        while num%prime == 0:
            num_list.append(prime)
            num /= prime
    return num_list

print(analysis(600851475143))

结果：[1, 71, 839, 1471, 6857]
最大质数：6857
运行时间：0.00500798

li1347zhen

#include<stdio.h>
#include<math.h>
int prime(long long int  x);
long long int nextprime(long  long int x);
int main()
{
        long int x=2;
        long long int divisor = x;
        long long  int 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为素数
{
        long  int 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

#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

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

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])
>>>
[71, 839, 1471, 6857]
Running time =  0.113600015640
Largest prime factor is  6857

塔利班

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

输出        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

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

996982937

#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

大大大敏

#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

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))