Sieve of Eratosthenes

Lab C Intermediate 20 points

Read n (≤ 10000) and print the number of primes ≤ n and the largest one.

Input

One integer ≥ 2.

Output

count largest

Example

Input

Output

10 29

Sample input available Sample output available

Editor

Hints

Mark the multiples of each prime, starting at i * i.

Solution explanation

Using a char array keeps memory small - one byte per number.

Show solution

#include <stdio.h>

char composite[10001];

int main() {
    int n, count = 0, largest = 0;
    scanf("%d", &n);
    for (int i = 2; i <= n; i++) {
        if (composite[i]) continue;
        count++;
        largest = i;
        for (int j = i * i; j <= n; j += i) composite[j] = 1;
    }
    printf("%d %d\n", count, largest);
    return 0;
}

Output

Answer