C - 如果它是素數，如何輕鬆測試？

Question

可能重複：
C - determine if a number is prime

有沒有辦法在C容易地測試所選擇的號碼是否是素數或不？

Answer 1

最簡單的方法是寫一個循環，如：

int is_prime(int num) 
{ 
    if (num <= 1) return 0; 
    if (num % 2 == 0 && num > 2) return 0; 
    for(int i = 3; i < num/2; i+= 2) 
    { 
     if (num % i == 0) 
      return 0; 
    } 
    return 1; 
} 

然後，您可以優化它，迭代到floor(sqrt(num))。

Answer 2

你可以嘗試使用埃拉托色尼的篩：

http://en.wikipedia.org/wiki/Sieve_of_Eratosthenes

輕鬆，你會發現這個算法的各種實現方式。

Answer 3

的最快的方法是預先計算了一下陣列（表示黃金/非高峯）在你感興趣的範圍內的所有可能的整數。對於32位無符號整數，這是隻有512M，這將很容易適應現代的地址空間（即使沒有，它也會快速查找文件）。

這幾乎肯定會比每次都通過篩子計算得更快。