[JAVA] 1-100,000사이의 모든 소수를 찾아 출력하는 프로그램

Question :

1-100,000 사이의 모든 소수를 찾아 출력하는 코드 작성하기

(소수: 1과 자기자신만을 약수로 갖는 자연수) 

 

 

Code : 

public class Code10 {

	public static void main(String[] args) {
		
		for(int n = 2; n<=100000 ; n++) {
			boolean isPrime = true; 
			for (int i = 2; i*i <= n && isPrime; i++) //8
				if (n % i == 0) 
					isPrime = false; //10
			if (isPrime)
				System.out.println(n);
			
		}
	}
}

Line8 : n/2까지 돌아도 되지만 굳이 약수를 발견했는데 n/2까지 돌 필요가 없으므로 root(n)의 값까지 돌린다. (square root)

Line10 : 정수로 나누어 떨어지면 소수가 아니기 때문에 false가 된다. 

 

 

Output : 

결과의 상단부만 캡쳐