3-12: 소수 찾기

소수 찾기 (findprime.cpp)

 

문제

---

주어진 숫자들 중 소수가 몇 개인지 찾아서 출력하는 프로그램을 작성하시오.  

입력

---

첫 줄에 수의 개수 N이 주어진다. N은 100이하이다. 다음으로 N개의 줄에 걸쳐 N개의 수가 주어지는데 수는 1,000 이하의 자연수이다.

 

출력

---

주어진 수들 중 소수의 개수를 출력한다.

 

예제 입력

4
1
3
5
7

예제 출력

3

import java.util.Scanner;

public class FindPrime {

    /**
     * 첫 줄에 수의 개수 N이 주어진다. N은 100이하이다. 다음으로 N개의 줄에 걸쳐 N개의 수가 주어지는데 수는 1,000 이하의 자연수이다.
     * 주어진 수들 중 소수의 개수를 출력한다.
     *
     * 4
     * 1
     * 3
     * 5
     * 7
     *
     * 3
     *
     * @param args
     */

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int N = sc.nextInt();
        int nums[] = new int[N];
        for (int i=0; i<N; i++){
            nums[i] = sc.nextInt();
        }


        int isPrime[] = new int[1001];
        isPrime[0] = -1;
        isPrime[1] = -1;
        isPrime[2] = 0;

        for (int i=2; i<isPrime.length; i++){
            //find lowest notPrimes
            if (isPrime[i] == 0){
                int source = i;
//                System.out.println(source + " is next prime");

                //mark all multiples of source to not prime
                for (int j=source*source; j<isPrime.length; j+=source){
//                    System.out.println(j + " is not prime");
                    isPrime[j] = -1;
                }
            }
        }

//        for (int i=0; i< isPrime.length; i++){
//            System.out.println("number " + i +" is prime? " + (isPrime[i]==0?"yes":"no"));
//        }

        int count=0;
        for (int i=0; i<N; i++){
            if (isPrime[nums[i]] == 0){
                count++;
            }
        }
        System.out.println(count);
    }
}