發表新討論
#42320: 使用Sieve of Eratosthenes(埃拉托斯特尼)的質數篩法(埃拉托斯特尼篩法)


spark960513@gmail.com (Sparkkk_)

學校 : 臺北市立成功高級中學
編號 : 204599
來源 : [180.217.7.6]
最後登入時間 ：
2024-11-01 07:42:50
a121. 質數又來囉 | From: [124.218.194.42] | 發表日期 : 2024-09-29 13:36

可以先看一下這一篇文章：如何有效率地寫程式判斷質數和尋找質數?

根據文章，若N是合數，則必有至少一個非1的因數<=N^1/2，我們利用這個性質尋找，則可減少大量不必要的時間。

-

-

-

-

-

-

-full codes

#include <iostream>
#include <vector>
#include <cmath>
using namespace std;

int main()
{
    int begin, end;

    while(cin>>begin>>end)
    {
        vector<int> listPrime;

        //check if prime
        for(int i = begin; i <= end; i++)
        {
            bool isPrime = true;

            // handle exceptions
            if(i == 2) listPrime.push_back(i);
            if(i % 2 == 0 || i == 1) continue;

            // compute until i^1/2
            for(int j = 3; j <= round(sqrt(i)); j++)  
            {
                if(i % j == 0) {
                    isPrime = false;
                    break;
                    }
            }
            // add to vector
            if(isPrime) listPrime.push_back(i);
        }
       
        // print result
        cout<<listPrime.size()<<endl;
    }
    return 0;
}

 
 
ZeroJudge Forum