수학1_1978 번 : 소수찾기 JAVA

방법1 : 기본 판별법

 

boolean isPrime(int num){
	if(num==1)
    	return false;
    
    for(int i=2;i<num;i++){
    	if(num%i==0){
        	return false;
        }
    }
    return true;
}

 

방법2 : 제곱근을 이용한 기본 판별법

 

boolean isPrime(int num){

    if(num==1){
		return false;
    }
    for(int i=2;i<=Math.sqrt(num);i++){
    	if(num%i==0)
        	return false;
    }
    return true;
}

 

방법3 : 에라토스테스이 체

boolean[] makePrime(int num){
	boolean[] prime = new boolean[num+1];
    prime[0] = true;
    prime[1] = true;
    prime[2] = false;
    for(int i=2;i<=Math.sqrt(num);i++){
    	
        int j = 1;
        while(i*j<=num){
        	if(prime[i*j]==false){
            	j++;
                continue;
            }
            prime[i*j] = true;
            j++;
        }
        return prime;
    }
}

 

문제 풀이는 제곱근을 이용하여 풀었다.

 

import java.io.*;
import java.util.StringTokenizer;

public class Main{
    public static void main(String[] args)throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        br.readLine();
        int count = 0;
        StringTokenizer st = new StringTokenizer(br.readLine()," ");
        
        while(st.hasMoreTokens()){
            boolean isPrime = true;
            
            int num = Integer.parseInt(st.nextToken());
            
            if(num==1)
                continue;
            for(int i=2;i<=Math.sqrt(num);i++){
                if(num%i==0){
                    isPrime = false;
                    break;
                }
            }
            if(isPrime)
                count++;
        }
        System.out.print(count);
    }
}