C++-এ ১ থেকে n পর্যন্ত প্রাইম সংখ্যাদের যোগফল

প্রাইম সংখ্যা যোগফল সমস্যা

১ থেকে n পর্যন্ত সব প্রাইম সংখ্যার যোগফল বের করতে হবে। প্রাইম সংখ্যা হলো যেগুলোর শুধু দুটি গুণক থাকে: ১ এবং সংখ্যাটি নিজে।

উদাহরণ: n = 15 → প্রাইম: ২, ৩, ৫, ৭, ১১, ১৩ → যোগফল = ৪১

পদ্ধতি ১: সাধারণ লুপ (O(n√n))

bool isPrime(int n) {
    for(int i = 2; i * i <= n; i++)
        if(n % i == 0) return false;
    return true;
}

int findPrimeSum(int n) {
    int sum = 0;
    for(int i = 2; i <= n; i++)
        if(isPrime(i)) sum += i;
    return sum;
}

পদ্ধতি ২: সিভ অফ এরাটোস্থেনিস (O(n log log n))

বহুত বড় n এর জন্য দ্রুত।

int findPrimeSum(int n) {
    vector<bool> isPrime(n + 1, true);
    isPrime[0] = isPrime[1] = false;
    for(int i = 2; i * i <= n; i++)
        if(isPrime[i])
            for(int j = i * i; j <= n; j += i)
                isPrime[j] = false;
    int sum = 0;
    for(int i = 2; i <= n; i++)
        if(isPrime[i]) sum += i;
    return sum;
}

C++ কোড উদাহরণ

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

int findPrimeSum(int n) {
    vector<bool> isPrime(n + 1, true);
    isPrime[0] = isPrime[1] = false;
    for(int i = 2; i * i <= n; i++)
        if(isPrime[i])
            for(int j = i * i; j <= n; j += i)
                isPrime[j] = false;
    int sum = 0;
    for(int i = 2; i <= n; i++)
        if(isPrime[i]) sum += i;
    return sum;
}

int main() {
    int n = 15;
    cout << "The sum of prime numbers between 1 to " << n << " is " << findPrimeSum(n);
    return 0;
}

আউটপুট

The sum of prime numbers between 1 to 15 is 41