// Assignment 01#02 due date 6/5/2018
// Page 106 Prime Numbers
// #08 Michael Y. C. Shih @ 107 Android Programming Class, EEC, UCH
 
import java.util.Scanner;
import java.util.Arrays;
 
class p106 {
 
	public static void main(String[] args) {
		// TODO Auto-generated method stub
		Scanner scan = new Scanner(System.in);
		System.out.print("Enter an integer: ");
		int number = scan.nextInt();
		scan.close();
 
		boolean[] isPrime = new boolean[number + 1];
		Arrays.fill(isPrime, true); // first assume all integers are prime.
		isPrime[0] = isPrime[1] = false; // it's known 0 and 1 are not prime.
		for (int i = 2;i < isPrime.length;i++) {
			if (isPrime[i]) { // if the number is a prime, mark all its multiples not prime.
				for (int j = 2;i * j < isPrime.length;j++) {
					isPrime[i * j] = false;
				}
			}
		}
		System.out.println("Prime Numbers from 1 to " + number + " are:");
		for (int k = 1;k < isPrime.length;k++) {
			if (isPrime[k])
				System.out.print(k + " ");
		}
	}
}