Re: [語法] 尋找2~1000的質數的語法討論

看板C_and_CPP (C/C++)作者danielguo (Daniel Guo)時間16年前 (2009/09/15 04:45)推噓0(0推 0噓 1→)

留言1則, 1人參與討論串3/6 (看更多)

剛剛寫了一下篩法和一般除法判斷的 code 除法判斷直接用剛剛檢查過是質數的數字來除, 可以省些時間, 用 6n +- 1 篩法不判斷偶數的部分在 n < 10,000,000 的時候都很快, 再上去篩法的速度就明顯的較快~ #include <iostream> #include <algorithm> #include <cmath> #include <ctime> using namespace std; const int MAX_N = 10000000; int pTable[MAX_N + 1], pTableCount; bool sieveBuffer[MAX_N / 2 + 1]; void DivideMethod(int n); void SieveMethod(int n); int main() { int i; clock_t startClock; double secUsed1, secUsed2; startClock = clock(); DivideMethod(10000000); secUsed1 = (clock() - startClock) / (double)CLOCKS_PER_SEC; startClock = clock(); SieveMethod(10000000); secUsed2 = (clock() - startClock) / (double)CLOCKS_PER_SEC; cout << secUsed1 << endl << secUsed2 << endl; return 0; } void DivideMethod(int n) { int i, j, sqrtI, round; bool isPrime; // pTable is output pTable[0] = 2; pTable[1] = 3; pTableCount = 2; for (i = 5; i <= n; i += 6) { for (round = 0; round < 2; round++) { // (round == 0) is 6n - 1 if (round == 1) { // 6n + 1 round i += 2; } sqrtI = (int)sqrt(i + 0.2f); isPrime = true; for (j = 0; (j < pTableCount) && (sqrtI >= pTable[j]); j++) { // Check for factor until sqrtI using table if (i % pTable[j] == 0) { isPrime = false; break; } } if (isPrime) { pTable[pTableCount] = i; pTableCount++; } } // Finish 6n + 1 round i -= 2; } } void SieveMethod(int n) { int i, j, sqrtN; sqrtN = (int)sqrt(n + 0.2f); DivideMethod(sqrtN); // Initialize buffer for (i = 0; i <= n / 2; i++) { sieveBuffer[i] = true; } // Sieve of Eratosthenes for (i = 1; i < pTableCount; i++) { for (j = pTable[i] * 3; j <= n; j += pTable[i] * 2) { sieveBuffer[j / 2] = false; } } // pTable is output pTable[0] = 2; pTableCount = 1; for (i = 3 / 2; i < n / 2; i++) { if (sieveBuffer[i]) { pTable[pTableCount] = i * 2 + 1; pTableCount++; } } } -- ※ 發信站: 批踢踢實業坊(ptt.cc) ◆ From: 76.170.79.35 ※ 編輯: danielguo 來自: 76.170.79.35 (09/15 04:46)

Re: [語法] 尋找2~1000的質數 的語法討論

Re: [語法] 尋找2~1000的質數的語法討論