尋找素數的程序我想找到介于0和長變量之間的素數，但我無法獲得任何輸出。該計劃是using System;using System.Collections.Generic;using System.Linq;using System.Text;namespace ConsoleApplication16{
class Program
{
void prime_num(long num)
{
bool isPrime = true;
for (int i = 0; i <= num; i++)
{
for (int j = 2; j <= num; j++)
{
if (i != j && i % j == 0)
{
isPrime = false;
break;
}
}
if (isPrime)
{
Console.WriteLine ( "Prime:" + i );
}
isPrime = true;
}
}
static void Main(string[] args)
{
Program p = new Program();
p.prime_num (999999999999999L);
Console.ReadLine();
}
}}任何人都可以幫助我找出程序中可能出現的錯誤嗎？
3 回答
千巷貓影
TA貢獻1829條經驗 獲得超7個贊
您可以使用近似最佳的試驗分割篩在一條（長）線上更快地完成此操作，如下所示：
Enumerable.Range(0, Math.Floor(2.52*Math.Sqrt(num)/Math.Log(num))).Aggregate(
Enumerable.Range(2, num-1).ToList(),
(result, index) => {
var bp = result[index]; var sqr = bp * bp;
result.RemoveAll(i => i >= sqr && i % bp == 0);
return result;
});這里使用的素數的近似公式是π(x) < 1.26 x / ln(x)。我們只需要通過不大于的素數進行測試x = sqrt(num)。
請注意，Eratosthenes的篩網比試驗分區具有更好的運行時間復雜度（num如果正確實施，應該更快地運行更大的值）。
浮云間
TA貢獻1829條經驗 獲得超4個贊
試試這個：
void prime_num(long num){
// bool isPrime = true;
for (long i = 0; i <= num; i++)
{
bool isPrime = true; // Move initialization to here
for (long j = 2; j < i; j++) // you actually only need to check up to sqrt(i)
{
if (i % j == 0) // you don't need the first condition
{
isPrime = false;
break;
}
}
if (isPrime)
{
Console.WriteLine ( "Prime:" + i );
}
// isPrime = true;
}}
繁星淼淼
TA貢獻1775條經驗 獲得超11個贊
您只需要檢查奇數除數，直到數字的平方根。換句話說，你的內循環需要開始：
for (int j = 3; j <= Math.Sqrt(i); j+=2) { ... }一旦發現數字不是素數，你也可以打破這個功能，你不需要檢查任何更多的除數（我看你已經這樣做了?。?。
這僅在num大于2時才有效。
沒有Sqrt
您可以通過保持運行總和來完全避免Sqrt。例如：
int square_sum=1;for (int j=3; square_sum<i; square_sum+=4*(j++-1)) {...}這是因為數字1+（3 + 5）+（7 + 9）的總和將給出一系列奇數正方形（1,9,25等）。因此j代表了平方根square_sum。只要square_sum不到i那么j小于平方根。
- 3 回答
- 0 關注
- 552 瀏覽
添加回答
舉報
0/150
提交
取消