[JAVA/코딩테스트] 소수 구하기

문제

1. 소수구하기

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

public class Main {
	
	public void solution(int num) {
		// 소수의 개수
		int count = 0;
		// 2부터 입력받은 숫자까지
		for(int i=2; i<=num; i++) {
			// 소수이면 true
			boolean isPrime = true;
			// 2부터 i/2까지 나눴을때 나누어지는 숫자가 존재하지 않으면 소수이다.
			for(int j=2; j*j<=i; j++) {
				// 계속 나눠서 나눠질때 소수가 아니다.
				if(i % j == 0) {
					// 소수가 아님.
					isPrime = false;
					break;
				}
				
			}
			// 소수이면
			if(isPrime) {
				count ++;
			}
		}
		
		System.out.print(count);

	}

	public static void main(String args[]) {
        Main main = new Main();
		Scanner in= new Scanner(System.in);
        int num = in.nextInt();
		main.solution(num); 
	}

}

2. 에라토스테네스 체

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

public class Main {
	
	public int solution(int num) {
		// 소수의 개수
		int count = 0;
		
		int[] ch = new int[num+1];
		for(int i=2; i<=num; i++) {
			if(ch[i]==0) {
				count ++;
				for(int j=i; j<=num; j=j+i) {
					ch[j] = 1;
				}
			}
		}
		
		return count;

	}

	public static void main(String args[]) {
        Main main = new Main();
		Scanner in= new Scanner(System.in);
        int num = in.nextInt();
		System.out.println(main.solution(num)); 
	}

}