소수 구하기 개선점

소수구하기 개선점

 

1. 짝수와 1은 소수가 아니다.
2. 판단할수의 제곱근이하의 소수들로 안나눠 진다면 소수이다.  ...=> 소수의 제곱<판단할수 로 범위를 축소 할 수 있다. 
   • ex.. 9가 소수인지 판별하려면 9의 제곱근 3 이하의 소수들 (3,2)로 나눠서 나누어 진다면 소수가 아니다.
   • 제곱근이 정수로 떨어지지 않는다면 내림 해서 생각.
3. 소수의 배수는 소수가 아니다. == 에라토스테네스의 체

(24.3.15일 추가)

2번항목을 그냥 아 그런가보다하고 넘어갔는데 다시 해보려니 이해가 안되서.. 추가로 찾아봤다.

• 약수의 특성을 이용하면 연산횟수를 감소 시키는 것이가능하다. 
  • 특정 수 N의 약수들을 일렬로 나열 했을때, 그 . 중가운데 수를 중심으로 약수가 대칭이 된다
    • 36을 예로 들어보자면 1,2,3,4,6 까지만 알아도 나머지 약수를 알 수있다는뜻.
    • 중심수는 어떻게 구하나면... N의 제곱근을 이용해서 구하면 된다.
  • 반절만 알아도 된다는 것.. 그것은 ... 반절만 판단해도 된다는 뜻이다
    • 36을 예를들어서 소수를 찾을때 1~6까지만 나누어봐서 나눠지는지 안나눠 지는지 판단하면 된다
    • 36이 4로도 나누어떨어진다면 그것과 대응 되는 9와도 나누어떨어진다고 알 수 있기 때문이다.
  • 이와 유사한 개념을 들고와서 수소 판단에 사용 할수 있다는뜻..

 

---

 

 

---일단은 2번개선 까지---

package 구현.자바알고리즘.기본자료구조;

public class PrimeNumber3 {
    public static void main(String[] args) {
        int counter =0;
        int ptr =0;
        int[] prime = new int[500];

        prime[ptr++]=2;
        prime[ptr++]=3;

        for (int n=5;n<=1000;n+=2){
            boolean flag = false;
            for(int i=1;prime[i]*prime[i]<=n;i++){
                counter+=2;
                // 지정한 소수로 나누어 떨어지면 소수가 아님
                if(n%prime[i]==0){
                    flag=true;
                    break;
                }
            }
            if(!flag){ // 마지막까지 나누어 떨어지지 않음 == 소수이다.
                prime[ptr++]=n;
                counter++;
            }
        }
        for(int i=0;i<ptr;i++){
            System.out.println(prime[i]);
        }
        System.out.printf("곱셈과 나눗셈을 수행한 횟수 : %d",counter);
    }
}