輸入大數字時命令終止

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（不是質數）的輸入崩潰。