Loading...
Loading...
Loading...
A college maths club is printing raffle tickets. Only ticket numbers that are prime get a prize. A prime is a whole number greater than 1 whose only divisors are 1 and itself.
The tickets are numbered 1 to n. Print how many prime numbers there are from 1 to n, and their total.
Example 1
Input
10
Output
4 17
The primes are 2, 3, 5 and 7. Their sum is 17.
Example 2
Input
1
Output
0 0
1 is not a prime, so there are none.
Try the problem first. Open one hint at a time.
Checking each number on its own by trial division is too slow for 10^7 numbers. Work on all numbers at once.
Keep a boolean array. When you reach a number that is still unmarked, it is prime: mark all its multiples as not prime.
For a prime p, start marking at p × p, because smaller multiples were already marked by smaller primes. Compute p × p as a long.
Add the primes in a long: the sum up to 10^7 is far bigger than the int limit.
Write your Java code, run it on the examples and submit it to hidden tests.
Solve in the editor