程序编译但不执行

Question

我编译了程序，但是当我给了输入= 600851475143没有结果出现。程序找到最大的素因子（13195的素因子是5,7,13和29）。什么是数字600851475143的最大素因子？） 出了什么问题？

#include<stdio.h> 


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

int main(){ 
    unsigned long n,i,lpf; 
    scanf("%ld",&n); 
    for(i=2;i<n;i++){ 
     if(n%i==0){ 
      if(isprime(i)==1){ 
      lpf=i;} 
     } 
    } 
    printf("%ld",lpf); 
    return 0; 
} 

Answer 1

你有一个for循环运行大致您输入的号码，i云时代从2到n-1。在那个循环中，你调用一个函数，该函数运行大约i次，这与循环中的i相同。这意味着您的程序会在n^2数学计算中执行，其中n是您的输入。如果输入12位数字，则n^2是24位数字的大小，对于某个程序，执行10^24计算需要很长时间。所以你的程序运行，它只是计算。

Answer 2

正如其他人已经说过的：你不需要走整条道路。上升到n的平方根就足够了，每次找到一个因子时，您也可以自己减少n的值。

稍微快一点的方法，虽然与天真版本相同的时间复杂性，但是使用轮子。这里使用的轮子是11个粗略数字之间的距离（加上之前的素数和下一轮的偏移量）。

一起：

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

#define ISPRIME(x) isprime(x) 
//#define ISPRIME(x) isprime_wheel(x) 

static int wheel[] = { 
1, 2, 2, 4, 2, 4, 2, 4, 6, 2, 6, 4, 2, 4, 6, 6, 2, 6, 4, 2, 6, 4, 6, 8, 4, 2, 
4, 2, 4, 14, 4, 6, 2, 10, 2, 6, 6, 4, 2, 4, 6, 2, 10, 2, 4, 2, 12, 10, 2, 4, 2, 
4, 6, 2, 6, 4, 6, 6, 6, 2, 6, 4, 2, 6, 4, 6, 8, 4, 2, 4, 6, 8, 6, 10, 2, 4, 6, 
2, 6, 6, 4, 2, 4, 6, 2, 6, 4, 2, 6, 10, 2, 10, 2, 4, 2, 4, 6, 8, 4, 2, 4, 12, 
2, 6, 4, 2, 6, 4, 6, 12, 2, 4, 2, 4, 8, 6, 4, 6, 2, 4, 6, 2, 6, 10, 2, 4, 6, 2, 
6, 4, 2, 4, 2, 10, 2, 10, 2, 4, 6, 6, 2, 6, 6, 4, 6, 6, 2, 6, 4, 2, 6, 4, 6, 8, 
4, 2, 6, 4, 8, 6, 4, 6, 2, 4, 6, 8, 6, 4, 2, 10, 2, 6, 4, 2, 4, 2, 10, 2, 10, 
2, 4, 2, 4, 8, 6, 4, 2, 4, 6, 6, 2, 6, 4, 8, 4, 6, 8, 4, 2, 4, 2, 4, 8, 6, 4, 
6, 6, 6, 2, 6, 6, 4, 2, 4, 6, 2, 6, 4, 2, 4, 2, 10, 2, 10, 2, 6, 4, 6, 2, 6, 4, 
2, 4, 6, 6, 8, 4, 2, 6, 10, 8, 4, 2, 4, 2, 4, 8, 10, 6, 2, 4, 8, 6, 6, 4, 2, 4, 
6, 2, 6, 4, 6, 2, 10, 2, 10, 2, 4, 2, 4, 6, 2, 6, 4, 2, 4, 6, 6, 2, 6, 6, 6, 4, 
6, 8, 4, 2, 4, 2, 4, 8, 6, 4, 8, 4, 6, 2, 6, 6, 4, 2, 4, 6, 8, 4, 2, 4, 2, 10, 
2, 10, 2, 4, 2, 4, 6, 2, 10, 2, 4, 6, 8, 6, 4, 2, 6, 4, 6, 8, 4, 6, 2, 4, 8, 6, 
4, 6, 2, 4, 6, 2, 6, 6, 4, 6, 6, 2, 6, 6, 4, 2, 10, 2, 10, 2, 4, 2, 4, 6, 2, 6, 
4, 2, 10, 6, 2, 6, 4, 2, 6, 4, 6, 8, 4, 2, 4, 2, 12, 6, 4, 6, 2, 4, 6, 2, 12, 
4, 2, 4, 8, 6, 4, 2, 4, 2, 10, 2, 10, 6, 2, 4, 6, 2, 6, 4, 2, 4, 6, 6, 2, 6, 4, 
2, 10, 6, 8, 6, 4, 2, 4, 8, 6, 4, 6, 2, 4, 6, 2, 6, 6, 6, 4, 6, 2, 6, 4, 2, 4, 
2, 10, 12, 2, 4, 2, 10, 2, 6, 4, 2, 4, 6, 6, 2, 10, 2, 6, 4, 14, 4, 2, 4, 2, 4, 
8, 6, 4, 6, 2, 4, 6, 2, 6, 6, 4, 2, 4, 6, 2, 6, 4, 2, 4, 12, 2, 12 
}; 

int isprime_wheel(unsigned long n) 
{ 
    unsigned long isqrt = (unsigned long) (floor(sqrt(n)) + 1); 
    unsigned long start = 5, factor = 2; 
    int wlen = sizeof(wheel)/sizeof(int); 
    int next = 0; 
    if(n == 2){ 
    return 1; 
    } 
    if ((n & 1) == 0) { 
    return 0; 
    } 
    if (isqrt * isqrt == n) { 
    return 0; 
    } 
    while (factor < isqrt) { 
    if (n % factor == 0) { 
     return 0; 
    } 
    factor += (unsigned long) wheel[next]; 
    next++; 
    if (next == wlen) { 
     next = start; 
    } 
    } 

    return 1; 
} 

unsigned long primefactors(unsigned long n) 
{ 
    unsigned long start = 5, factor = 2; 
    unsigned long biggest = 0; 
    int wlen = sizeof(wheel)/sizeof(int); 
    int next = 0; 
    if (n == 1) { 
    return 0; 
    } 
    if (n == 2 || n == 3) { 
    return n; 
    } 

    while (factor <= n) { 
    while (n % factor == 0) { 
     biggest = factor; 
     n /= factor; 
    } 
    factor += (unsigned long) wheel[next]; 
    next++; 
    if (next == wlen) { 
     next = start; 
    } 
    } 
    if (n > 1 && biggest == 0) { 
    return n; 
    } 

    return biggest; 
} 



int isprime(unsigned long n) 
{ 
    unsigned long i; 
    unsigned long isqrt = (unsigned long) floor(sqrt(n)) + 1; 

    for (i = 2; i < isqrt; i++) { 
    if ((n % i) == 0) { 
     return 0; 
    } 
    } 
    return 1; 
} 

#include <time.h> 
int main() 
{ 
    unsigned long n, i, lpf = 0, wheelfactor = 0; 
    clock_t start,stop; 

    if(scanf("%lu", &n) != 1){ 
    fprintf(stderr,"Must be a positive, small integer \n"); 
    exit(EXIT_FAILURE); 
    } 

    start = clock(); 
    wheelfactor = primefactors(n); 
    stop = clock(); 
    printf("WHEEL Time %.10f seconds\n", (double) (stop - start)/CLOCKS_PER_SEC); 
    printf("WHEEL %lu\n",wheelfactor); 

    start = clock(); 
    if (n == 1) { 
    puts("0"); 
    goto END; 
    } 
    if (n == 2 || ISPRIME(n) == 1) { 
    printf("NAIVE %lu (n is prime, next print must show 0)\n", n); 
    goto END; 
    } 
    for (i = 2; i < n/2 + 1; i++) { 
    if (ISPRIME(i) == 1 && n % i == 0) { 
     //printf("PRIME %lu\n", i); 
     lpf = i; 
     n /= i; 
     // n might be down to 2 and isprime(2) returns true 
     // but only odd primes are allowed at this point 
     if (ISPRIME(n) == 1 && n > lpf) { 
     //printf("ISPRIME %lu\n", n); 
     lpf = n; 
     } 
    } 
    } 
END: 
    stop = clock(); 

    printf("NAIVE Time %.10f seconds\n", (double) (stop - start)/CLOCKS_PER_SEC); 
    printf("NAIVE %lu\n", lpf); 
    return 0; 
} 

你可能会与一些大型复合材料例如像试试吧：11529215046068460看看哪个更极端一点，需要很大的耐心，在运行时的不同，或1152921123 - 它可能需要几分钟。

Answer 3

早些时候，我注意到，我原来的解决方案：

仍然需要太长600851475143所以它的时间来寻找一个 完全不同的算法

一个搜索的SO变成了efficient ways of finding the largest prime factor of a number。

这里有一个简单而快速的解决方案基于@ under5hell在该网页上的答案：

#include <stdio.h> 
#include <assert.h> 

int main() 
{ 
    unsigned long long number; 

    assert(sizeof(number) * 8 >= 64); // make sure we've enough bits 

    scanf("%llu", &number); 

    for (unsigned long long divisor = 2; divisor < number; divisor++) { 
     if (number % divisor == 0) { 
      number /= divisor--; // decrement to remove multiples 
     } 
    } 

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

    return 0; 
} 

哪可以找到600851475143最大的主要因素在几分之一秒：

输出

> ./a.out 
600851475143 
6857 
> 

故事的道德似乎是搜索所以在你查询之前！