Editorialist: akshayakgec
DIFFICULTY:
EASY
PREREQUISITES:
number theory
PROBLEM:
for every prime number from 1 to n you have to find the prime number in the range from 1 to n and find the sum and print the answer.
QUICK EXPLANATION:
Just implement the seive and find the prime number in the range and take there sum in a variable and print the answer
EXPLANATION:
Here we just have to find the sum of all prime numbers from 1 to the given number of old coins. We can apply sieve to find all prime numbers from 1 to the given number of old coins.
Editorialist's Solution
#include <bits/stdc++.h>
#define ll long long
using namespace std
int main() {
int t; cin >> t;
ll sieve[1000001];
for(ll i=0;i<=1000000;i++){
sieve[i]=1;
}
sieve[0]=sieve[1]=0;
for(ll i=2;i<=sqrt(1000000);i++){
if(sieve[i]==1){
for(ll j=i*i;j<=1000000;j+=i) {
sieve[j]=0;
}
}
}
while(t--) {
ll coins;
cin >> coins;
ll chocolates = 0;
for(ll i=1; i<=coins; i++){
if(sieve[i] == 1) {
chocolates += i;
}
}
cout << chocolates << "\n";
}
return 0;
}