尋找素?cái)?shù)的程序我想找到介于0和長(zhǎng)變量之間的素?cái)?shù)，但我無(wú)法獲得任何輸出。該計(jì)劃是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();
}
}}任何人都可以幫助我找出程序中可能出現(xiàn)的錯(cuò)誤嗎？
3 回答
千巷貓影
TA貢獻(xiàn)1829條經(jīng)驗(yàn) 獲得超7個(gè)贊
您可以使用近似最佳的試驗(yàn)分割篩在一條（長(zhǎng)）線上更快地完成此操作，如下所示：
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;
});這里使用的素?cái)?shù)的近似公式是π(x) < 1.26 x / ln(x)。我們只需要通過(guò)不大于的素?cái)?shù)進(jìn)行測(cè)試x = sqrt(num)。
請(qǐng)注意，Eratosthenes的篩網(wǎng)比試驗(yàn)分區(qū)具有更好的運(yùn)行時(shí)間復(fù)雜度（num如果正確實(shí)施，應(yīng)該更快地運(yùn)行更大的值）。
浮云間
TA貢獻(xiàn)1829條經(jīng)驗(yàn) 獲得超4個(gè)贊
試試這個(gè)：
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貢獻(xiàn)1775條經(jīng)驗(yàn) 獲得超11個(gè)贊
您只需要檢查奇數(shù)除數(shù)，直到數(shù)字的平方根。換句話說(shuō)，你的內(nèi)循環(huán)需要開(kāi)始：
for (int j = 3; j <= Math.Sqrt(i); j+=2) { ... }一旦發(fā)現(xiàn)數(shù)字不是素?cái)?shù)，你也可以打破這個(gè)功能，你不需要檢查任何更多的除數(shù)（我看你已經(jīng)這樣做了?。?/p>
這僅在num大于2時(shí)才有效。
沒(méi)有Sqrt
您可以通過(guò)保持運(yùn)行總和來(lái)完全避免Sqrt。例如：
int square_sum=1;for (int j=3; square_sum<i; square_sum+=4*(j++-1)) {...}這是因?yàn)閿?shù)字1+（3 + 5）+（7 + 9）的總和將給出一系列奇數(shù)正方形（1,9,25等）。因此j代表了平方根square_sum。只要square_sum不到i那么j小于平方根。
- 3 回答
- 0 關(guān)注
- 553 瀏覽
添加回答
舉報(bào)
0/150
提交
取消