[SWEA] 3131. 100만 이하의 모든 소수

문제

100만 이하의 모든 수를 구하는 문제

 

풀이방법

2, 3, 4, ..., i, ..., 1,000,000까지 소수검사를 한다. 

 

각 숫자를 소수 검사할 때, i의 제곱근까지만 나누어 지는지 확인하면 i가 소수인지 판별할 수 있다.

 

소스코드

package samsung;

import java.util.*;

public class s_3131 {
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		for(int i = 2; i < 1000000; i++) {
			int flag = 0;
			for(int j = 2; j <= Math.sqrt(i); j++) {
				if(i % j == 0) {
					flag = 1;
					break;
				}
			}
			if(flag == 0)
				System.out.print(i + " ");
		}
	}
}