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

ietar

python 6857

取约数算法优化 只取质数 记录取到的约数 i  下次取约数从 i 开始
手写个轮子用来计时 优化效果很有限 可能要更大的数才见效


>>> timef(p3(),number=10000)
0.0010133860000109962
>>> timef(p3_mix(),number=10000)
0.000952252999979919

def p3_mix():
    import math 
    a = 600851475143
    def p3_get_prime(n):
        return int(3*n+1+(math.sin(math.pi*n/2))**2)

    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
    
    def p3_1_mix(n,num=1,i=2):
        if is_prime(n):
            return n
        while i < a//2+1:
            if not n%i:  # n被i整除
                return p3_1_mix(n/i,num,i)
            else:  # n无法被i整除
                if i == 2:
                    i = 3
                elif i == 3:
                    i = p3_get_prime(num)
                else:
                    num += 1
                    i=p3_get_prime(num)
    print(p3_1_mix(a))
                

doodu

冷钟天 发表于 2016-7-4 15:57
n=600851475143
a=2
while n!=a:

1，为什么a递增以后的值，没有在素数范围内也行？？？
2，为什么不断缩小的n，不再使用比a小的值（素数）取商？？？

假如n初始为100，a初始为2：
      n            a
1， 100         2<--素数
2、 50          3<--素数
3、 50          4
4、 50          5<--素数
5， 10           6
6， 10           7<--素数
7， 10           8
8， 10           9
9， 10           10

11才是质数啊？？？

micolar

C 不知道为啥不稳定 难道是虚拟机的原因？

#include<stdio.h>
int a[1000001];
int main(){
        int i,j;
        for(i = 2; i <= 500000;i++){
                for(j = i * 2;j <=1000000;j += i)
                        a[j] = 1;
        }
        for(i = 999999;i >= 2; i-- )
        if(a[i] == 0 && 600851475143%i == 0){
                printf("%d",i);
                return 0;
        }
        
        printf("600851475143");
        
        return 0;
}

Weiwei7

% %Euler_3  What is the largest prime factor of the number 600851475143 ?
% % The prime factors of 13195 are 5, 7, 13 and 29.

x=input('please input a number\n');
l=0;
for i=3:2:x
    if isprime(i)==1 && mod(x,i)==0
            l=i;
            x=x/i;  
            disp(l);
    end         
end

永恒的蓝色梦想

num = 600851475143
divisor = 3


while num != 1:
    if num % divisor:
        divisor += 2
    else:
        num //= divisor


print(divisor)

RRRex

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


int main()
{
    int begin_time, end_time;
    begin_time = clock();

    int biggest = 0;
    _Bool not_prime = 0;
    for (int i = 3; i < sqrt(600851475143); i += 2)
    {
        if (600851475143 % i == 0)
        {
            for (int j = 3; j < sqrt(i); j += 2)
            {
                if (i % j == 0)
                {
                    not_prime = 1;
                    break;
                }
            }
            if (!not_prime)
            {
                biggest = i;
            }
        }
    }
    printf("600851475143 的最大质数因子是%d\n", biggest);

    end_time = clock();
    printf("\n程序一共运行%dms\n", end_time - begin_time);

    return 0;
}

justjust001

#include <stdio.h>
#include <time.h>

int main()
{
        unsigned long long num = 600851475143;
        unsigned long long a, t;

        int begin = clock();
        for (a = 2; a < num; a++)
        {
                for (t = 2; t < a / 2; t++)
                        if (a % t == 0)
                                break;
                if ( t >= a / 2)
                        if (num % a == 0)
                        { 
                                num /= a;
                                a = 1;
                        }
        }
                
        printf("600851475143 最大质数因子 = %llu\n", num);
        int end = clock();
        printf("time = %dms\n", end - begin);
        system("pause");
        return 0;
}

华博文

import re
import math
import time

method = re.compile("[^0-9]")
def forma(miao):
    tim = list()
    ge_m = float("{:.10f}".format(miao))
    ge_h = float("{:.10f}".format(ge_m / 3600))
    ge_h_guo = float("{:.10f}".format(miao % 3600))
    ge_f = float("{:.10f}".format(ge_h_guo / 60))
    ge_miao = float("{:.10f}".format(ge_h_guo % 60))
    if ge_h > 1:
        tim.append(int(ge_h))
    if ge_f > 1 or len(tim) != 0:
        tim.append(int(ge_f))
    tim.append(ge_miao)
    return tim



da = int()
ran = input("请输入一个整数 , 求最大的质数因子：")
tex = method.search(ran)
if not tex:
   
    ship = int(ran)#600851475143
    chu = int(math.sqrt(ship))
    time_start = time.perf_counter()
    tiger_chu = sorted([each for each in range(chu , 0 , -1) if ship % each == 0] , reverse = True)
    rabbit_zhi = [[car for car in range(2 , int(each)) if each % car == 0] for each in sorted(tiger_chu , reverse = True)]
    da = tiger_chu[rabbit_zhi.index([])]

    miao = time.perf_counter() - time_start
    lai = forma(miao)
    if len(lai) == 1:
        print("最大值为：" + str(da) + "\n运行时间为：{:.2f}秒".format(lai[0]))
    elif len(lai) == 2:
        print("最大值为：" + str(da) + "\n运行时间为：{}分{}秒".format(lai[0] , lai[1]))
    else:
        print("最大值为：" + str(da) + "\n运行时间为：{}时{}分{}秒".format(lai[0] , lai[1] , lai[2]))
else:
    print("您输入的数值运行不了~~")


#我感觉我的效率还不错，欢迎大家来copy~~

天云TY

import tkinter as tk
x = 600851475143
i = 2
while True:
    
    if i >= x:  #当i > x时，x铁定除不尽i(当i = x 时，它就没意义了)，所以执行下列命令：
        break
    while x % i == 0: #当x % i == 0
        if i >= x:  #当i > x时，x铁定除不尽i(当i = x 时，它就没意义了)，所以执行下列命令：
            break
        else:
            x /= i

    else:
        i += 1
s = tk.Tk();tk.Label(s,text=x).pack();s.mainloop() #显示出答案

1666194196

#include <stdio.h>

void main(){
        //13195的所有质因数为5、7、13和29。
        //600851475143最大的质因数是？
        int i,a=13195,max=0;
        for(i=2;i<a;i++){//2到它本身-1的循环
                if(a%i==0){//如果能整除说明是他的因数
               
                        int j,flag=1;
                       
                        for(j=2;j<i;j++){//2到它本身-1的循环
                                if(i%j==0){//如果能整除说明有因数 ,标志为假 ，不输出
                                        flag=0;
                                }
                        }
                        if(flag){//如果没有能整除顺序执行下来flag=1，为真。打印出这个数
                                printf("质因数%d\n",i);
                                max=i;
                       
                        }
                }
        }
        printf("做大质因数=%d",max);
}

带上面具的孩纸

int main()
{
    unsigned long long int MPX;
    int MAX = 1;
    int i;

    printf("\nplease input number: ");
    scanf("%llu",&MPX);

    for(i = 2;i < MPX;i++)
    {
        if(MPX % i == 0)
        {
            MAX = MAX > i ? MAX : i;
           // printf("%d\t",i);
        }
    }
    printf("\n MAX=%d\n",MAX);

    return 0;
}

如有错误 请指正

杨扬阳羊洋

unsigned long long isprime(unsigned long long num)
{
    unsigned long long max=0;
    for(unsigned long long i=2;i<=(int)sqrt((double)num);i++)
    {
        if( (num%i)==0 )  {return 0;}
    }
    return 1;
}
unsigned long long max_factor(unsigned long long num)
{
    unsigned long long max=0,temp=0;
    for(unsigned long long j=2;j<=(int)sqrt((double)num);j++)
    {
        int n=0;
        if(num%j==0)    // 找出合数中的因子
        {
            if( isprime(j)==1 )
            {
                if(max<j){max=j;printf("prime=%llu\n",j);}
            }
            temp=num/j;
            if( isprime(temp)==1 )
            {
                if(max<temp){max=temp;printf("prime=%llu\n",temp);}
            }
        }
    }
    return max;
}

guoquanli

游客 218.17.207.x 发表于 2015-10-30 16:07
大数用了__int64类型

输出结果：

非常感谢您的分享，请教您一下，我在linux环境下运行您的这段代码提示：unknown  type  name '__int64',头文件<math.h>也包含了，问题在哪里了？

就是要努力呀

#include <stdio.h>
#include <time.h>

int main(void)
{
        int i = 2;
        long int a = 600851475143;
        time_t start, end;

        time(&start);

        while(a > 1)
        {
                if(a % i == 0)
                {
                        a /= i;

                        continue;
                }

                i++;
        }

        time(&end);

        printf("%ld的最大质因数为:%d\n", a, i);
        printf("time:%ld\n", end - start);

        return 0;
}
~                                                   

就是要努力呀

#include <stdio.h>
#include <time.h>

int main(void)
{
        int i = 2;
        long int a = 600851475143;
        time_t start, end;

        time(&start);

        while(a > 1)
        {
                if(a % i == 0)
                {
                        a /= i;
                }
                else i++;
        }

        time(&end);

        printf("600851475143的最大质因数为:%d\n", i);
        printf("time:%ld\n", end - start);

        return 0;
}

代号-K

这与第七题 类似，只做稍微修改即可得出答案 :6857

int calculatePrime(long long value)
{
    int array[100] = {0};
    array[0] = 2;
    int i = 1;
    int j = 3;
    int k = 0;
    int yes = 1;
    while(true)
    {
        if(array[i-1] >= value)
        {
            break;
        }
        else
        {
            k = 0;
            while( k < i)
            {
                if(j % array[k] == 0)
                {
                    yes = 0;
                    break;
                }
                k++;
            }
            if(yes && value % j == 0)
            {
                value /= j;
                array[i++] = j;
            }
        }
        j++;
        yes = 1;
    }
    return array[i-1];
}

int main(int argc, char *argv[])
{
    int sum = calculatePrime(600851475143);
    printf("%d\n",sum);
    return 0;
}

永恒的蓝色梦想

C++ 0ms

#include<iostream>
#include<cmath>
#include<cstdint>
using namespace std;



uint64_t maxPrimeDivisor(uint64_t num) {
    if (num < 2) {
        return 0;
    }

    while (!(num & 1)) {
        num >>= 1;
    }

    if (num != 1) {
        uint64_t divisor = 3, max = sqrt(num);

        while (divisor <= max) {
            if (num % divisor) {
                divisor += 2;
            }
            else {
                do {
                    num /= divisor;
                } while (!(num % divisor));

                if (num == 1) {
                    return divisor;
                }

                max = sqrt(num);
            }
        }

        return num;
    }

    return 2;
}



int main() {
    ios::sync_with_stdio(false);

    cout << maxPrimeDivisor(600851475143) << endl;
    return 0;
}

leon0149

71 839 1471 6857
0.002s

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

#define NUM 600851475143        // 常量定义

int isPrime(int x){
    /*
     * 判断是不是素数
     */
    int ret = 1;
    for (int i = 3; i < sqrt(x); i+=2) {
        if (x % i == 0)
            ret = 0;
    }

    return ret;
}

int isPrimeLong(long long x){
    /*
     * 判断是不是素数
     */
    int ret = 1;
    long double sqr = sqrt(x);
    for (long i = 3; i < sqr; i+=2) {
        if (x % i == 0)
            ret = 0;
    }

    return ret;
}

int main(void)
{
    int *array = NULL;
    long long *array2 = NULL;
    double sqr = sqrt(NUM);
    int cnt = 0;
    int cnt2 = 0;

    for (int i = 3; i < sqr; i+=2) {
        /*
         * 把这个数据分成两部分
         */
        if (NUM % i == 0){
            /*
             * 判断能不能被这个数据整除
             */
            if (isPrime(i)){
                /*
                 * 判断是不是素数
                 * 如果是
                 * 那么分配一个数据的内存
                 * 把这个素数放到数组array里面
                 */
                array = (int *)realloc(array, sizeof(int));
                array[cnt] = i;
                cnt++;
            }
            long long num = NUM / i;    // 如果上面i可以被整除那么 一定有另一个数匹配这个i
            if (isPrimeLong(num)){
                /*
                 * 判断这个另一个数是否是素数
                 * 如果是 那么分配一个数据的内存
                 * 因为数据可能比较大 所以用long long类型储存
                 * 把这个数放入long long 类型的数组array2里面
                 */
                array2 = (long long *)realloc(array2, sizeof(long long));
                array2[cnt] = i;
                cnt2++;
            }
        }
    }

    /*
     * 分别遍历两个数组
     */
    for (int i = 0; i < cnt; ++i) {
        printf("%d ", array[i]);
    }

    for (int i = 0; i < cnt2; ++i) {
        printf("%lld ", array2[i]);
    }

    free(array);    // 释放内存
    free(array2);

    return 0;
}

永恒的蓝色梦想

cupbbboom 发表于 2018-11-15 16:46
有没有跟我一样：先百度  合数 、质数因子，然后就有了百度  什么是质数？什么是因数？什么是整数、正整数? ...

这是小学的知识

永恒的蓝色梦想

guoquanli 发表于 2019-12-31 14:56
非常感谢您的分享，请教您一下，我在linux环境下运行您的这段代码提示：unknown  type  name '__int64', ...

把 __int64 改成 long long