Count the prime numbers from 2 to n, and print the largest of them.
What to build
A sieve of Eratosthenes that reports how many primes there are up to n.
Requirements
- Cross out the multiples of each prime, starting at its square.
- Count the numbers left, from 2 to
n. - Print the count and the largest prime.
Input
One number n (2 ≤ n ≤ 20000).
Output
The number of primes up to n and the largest one, separated by a space.
Constraints
2 ≤ n ≤ 20000.
Example
Input:
10
Output:
4 7
Why it works
A composite number has a prime factor no larger than its square root, so crossing out from p × p reaches every composite.
Examples
Example 1 · Input
10
Expected output
4 7
Example 2 · Input
2
Expected output
1 2
Hints
Hint 1
Use the sieve of Eratosthenes on a global array char composite[20001].
Hint 2
For each p with p * p <= n that is not crossed out, cross out p * p, p * p + p, ...
Hint 3
Then count what is left from 2 to n, and remember the last one.
Solution
Show one correct solution (try it yourself first)
#include <stdio.h>
char composite[20001]; // 1 = crossed out
int main(void) {
int n;
scanf("%d", &n);
for (int p = 2; p * p <= n; p++)
if (!composite[p])
for (int m = p * p; m <= n; m += p) composite[m] = 1;
int count = 0, largest = 0;
for (int i = 2; i <= n; i++) {
if (!composite[i]) {
count++;
largest = i;
}
}
printf("%d %d\n", count, largest);
return 0;
}