소수 구하기!!

 

소수구하는 방법 1: N√N 의 시간 복잡도 -> 2초 초과 x

 

임의의 자연수 N=16이라면 약수는 1,2,4,8,16 이 된다. 

*(pxq)

1x16 2x8 4x4 8x2 16x1

p와 q는 N의 약수이기 때문에 N을 임의의 수로 나누면 임의의 수가 √N 보다 작다면 결국 나머지는 √N 보다 클 수밖에 없다.  즉, p와 q중 하나는 반드시 √N 보다 작거나 같다.  √N 이하의 자연수 중에 나누어 떨어지는 수가 있다면 이는 1과 N을 제외한 다른 자연수가  N의 약수라는 의미이므로 소수가 아니게 됩니다. 

 

//소수 구하기 
	static boolean isPrime(int num) {
		   for(int i=2; i<=Math.sqrt(num); i++){
	            if(num%i == 0) return false;
		   }
	        return true;
	}

 

 

에라토스테네스의 체

2부터 √N 이하까지의 자연수 중 k를 제외한 k의 배수들을 제외시킨다. 

 

1.  2부터 소수를 구하고자 하는 구간의 모든 수를 나열한다.
2. 소수가 되는 수의 배수를 지우면 남은 건은 소수만 된다
3. 자기 자신을 제외한 2의 배수를 모두 지운다.
4. 남아 있는 수 가운데 3은 소수이므로 오른쪽에 3을 쓴다.
5. 자기 자신을 제외한 3의 배수를 모두 지운다.
6. 남아 있는 수 가운데 5는 소수이므로 오른쪽에 5를 쓴다.
7. 자기 자신을 제외한 5의 배수를 모두 지운다.
8. 위 과정을 반복

static void getPrime(int N){
		
		// 구하고자 하는 숫자 범위
        int N = 20
        
       //0과 1은 소수가 아니므로 false
        prime[0] = prime[1] = false;
        
        for(int i=2; i*i<=N; i++){      
            if(prime[i]){// prime[i]가 소수라면
                //i를 제외한 i의 배수들은 소수가 아니다. 
              	for(int j=i*i; j<=N; j+=i) prime[j]=false;             
            }        
        }    
        
    }