문제풀이 7번

입력 받은 숫자의 소수 판별

package _2;
import java.util.*;
public class Main {

	public static void main(String[] args) {
		// TODO Auto-generated method stub
		
	 Scanner sc = new Scanner(System.in);
	 
	 int a = 	sc.nextInt();
	 int count =0;
	 for(int i=1 ; i<=a ;i++)
	 {
		 if(a%i==0) count++;
		 
	 }
	 if(count==2) System.out.println(a+"는 소수 입니다 .");
	 else System.out.println(a+"는 소수가 아닙니다 .");
	}
}

소수 판별 -에라토스테네스의 체

1. 2부터 소수를 구하고자 하는 구간의 모든 수를 나열한다.

2. 2는 소수이므로 오른쪽에 2를 쓴다.

3. 자기 자신을 제외한 2의 배수를 모두 지운다.

4. 남아있는 수 가운데 3은 소수이므로 오른쪽에 3을 쓴다.

5. 자기 자신을 제외한 3의 배수를 모두 지운다.

6. 남아있는 수 가운데 5는 소수이므로 오른쪽에 5를 쓴다.

7. 자기 자신을 제외한 5의 배수를 모두 지운다.

8. 남아있는 수 가운데 7은 소수이므로 오른쪽에 7을 쓴다.

9. 자기 자신을 제외한 7의 배수를 모두 지운다.

10. 위의 과정을 반복하면 구하는 구간의 모든 소수가 남는다.

11.N의 제곱근(나누어 떨어지지 않는다면 보다 큰 자연수)보다 작은 소수의 배수를 모두 지우고 남는 수는 모두 소수

package _2;
import java.util.*;
public class Main {

	public static void main(String[] args) {
		// TODO Auto-generated method stub
		
		 Scanner sc = new Scanner(System.in); 
		 int n = 	sc.nextInt();
		 
		 boolean[] prime = new boolean[n+1];	
		 prime[0] = prime[1] = false;
		 for(int i=2 ; i<=n ; i++) 
		 {
			 prime[i] = true;
		 }
		 
		 for(int i =2 ; i*i<=n ; i++)
		 {
			 for(int j=i*i  ; j<=n ; j=j+i)
			 {
				 prime[j] = false;
			 }
		 }
		
		 System.out.print("1~n까지의 소수는 : ");
		for(int i=0 ; i<=n ; i++) 
		{
			if(prime[i] ==true) System.out.print(" "+i);
		}
		 
		 
	}
}