Sieve of Eratosthenes

Lab Java Intermediate 20 points

Read n (≤ 100000) 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

Java

Hints

Mark multiples of each prime starting at i * i.

Use long for i * i to avoid overflow.

Solution explanation

A boolean array marks composites; whatever stays unmarked is prime.

Show solution

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        boolean[] composite = new boolean[n + 1];
        int count = 0, largest = 0;
        for (int i = 2; i <= n; i++) {
            if (composite[i]) continue;
            count++;
            largest = i;
            for (long j = (long) i * i; j <= n; j += i) composite[(int) j] = true;
        }
        System.out.println(count + " " + largest);
    }
}

Output

Answer