输入大数字时命令终止

Question

当我尝试输入大量数字（约1000万）时，怎么会收到“命令已终止”的消息？该程序显示数字是否为素数。

见下面的代码：

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

int main (int argc, char *argv[]) 
{ 
    unsigned long long number; 
    bool prime (unsigned long long); 

    printf ("Enter a positive integer greater than 1: "); 
    scanf ("%llu", &number); 

    prime(number) ? 
     printf ("%llu is a prime.\n", number): 
     printf ("%llu is not a prime.\n", number); 

    return EXIT_SUCCESS; 
} 

bool prime (unsigned long long number) 
{ 
    unsigned long long i, j; 
    bool isPrime[number + 1]; 

    for (i = 2; i <= number; i++) 
     isPrime[i] = true; 

    for (i = 2; i <= number - 1; i++) 
     for (j = 1; i*j <= number; j++) 
     isPrime[i*j] = false; 

    return isPrime[number]; 
} 

Answer 1

的问题是，你试图堆栈比可用内存大上创建阵列isPrime。你应该在堆上而不是创建它，使用

bool *isPrime; 
isPrime = malloc((number + 1) * sizeof *isPrime); 

这样做只是一次很明显，不是每次调用函数prime

还要注意的是，如果你只是想知道，如果一个数是素数，你只需要搜索一个因子的数字的平方根 - 如果你找到一个因子，你就完成了。这使得您必须创建的数组的大小更易于管理 - 但它确实涉及对算法的一些更改。

事后你在逻辑决定什么是素数的问题 - 这意味着即使素数将被标记为非黄金的内环与j=1开始。以下是“略有改善”的代码 - 尽管还有更多你可以做，使之更好：

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

int main (int argc, char *argv[]) 
{ 
    unsigned long long number; 
    bool prime (unsigned long long); 

    printf ("Enter a positive integer greater than 1: "); 
    scanf ("%llu", &number); 

    prime(number) ? 
     printf ("%llu is a prime.\n", number): 
     printf ("%llu is not a prime.\n", number); 

    return EXIT_SUCCESS; 
} 

bool prime (unsigned long long number) 
{ 
    unsigned long long i, j, sq; 
    bool *isPrime; 
    sq = ceil(sqrt(number)); 
    isPrime = malloc((sq + 1)*sizeof *isPrime); 

    // generate primes up to the square root of the number 
    for (i = 2; i <= sq; i++) 
     isPrime[i] = true; 

    for (i = 2; i < sq; i++) { 
     // only need to mark multiples if this is a prime: 
     if(isPrime[i]) { 
     // start this loop at 2, not 1! 
     for (j = 2; i*j <= sq; j++) { 
      isPrime[i*j] = false; 
     } 
     } 
    } 

    for (i = 1; i < sq; i++) 
    { 
    if (isPrime[i] && number%i==0) return false; 
    } 

    return true; 
} 

基本测试：

gcc -Wall产生任何错误/警告

104729是素（它是）;代码不会与输入10000001（不是质数）的输入崩溃。