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

https://swexpertacademy.com/main/code/problem/problemDetail.do?problemLevel=3&contestProbId=AV_6mRsasV8DFAWS&categoryId=AV_6mRsasV8DFAWS&categoryType=CODE&problemTitle=&orderBy=RECOMMEND_COUNT&selectCodeLang=JAVA&select-1=3&pageSize=10&pageIndex=3 

SW Expert Academy

소수를 찾는 방법을 배웠음. 외워두자.

범위가 정해지면 해당범위까지를 for문으로 돌리고 각 수를 2부터 해당 수의 제곱근까지로 나눠준다. 이때 나눠지는 수가 있다면 소수가 아님. 끝까지 나눠지지 않으면 소수라는 뜻이므로 sb에 넣어준다.

 

내 코드

메모리 : 28832 KB

시간 : 496 ms

코드길이 : 541 B

 

[내 코드]

import java.util.Scanner;

public class Solution {
	
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		StringBuilder sb = new StringBuilder();
		
		for(int i = 2; i < 1000000; i++) {
			boolean isPrime = true;
			//2부터 i의 제곱근의 수로
			for(int j = 2; j <= Math.sqrt(i); j++) {
				//i가 나눠지면 소수가 아니란 뜻이므로
				if(i % j == 0) {
					isPrime = false;
					break;
				}
			}
			//나눠지지 않았다는 뜻이므로 소수임
			if(isPrime)
				sb.append(i).append(' ');
		}
		System.out.print(sb);
	}
}