소수 구하는 알고리즘 - 자바 코딩
코딩과 교육/전문코딩 2017. 11. 17. 17:25소수구하는 알고리즘
예전에 파이썬으로 했던 소수 알고리즘이다.
2개의 수를 넣으면 그 두 수 사이의 모든 소수를 찾아서 화면에 출력한다.
실제로 소수를 찾는 시간은 매우 빠르지만 너무 많은 수를 출력하게 되면 화면 출력시간때문에 지연시간이 길어진다.
2로 나누어 떨어지는 수는 소수가 아니므로 통과
3으로 나누어 떨어지는 수는 소수가 아니므로 통과
그러므로 3 이상의 모든 소수는 6k-1 또는 6k+1 에 해당한다. 모든 수에 대해서 % 연산을 수행하지 않고 6k-1, 6k+1 에 대해서만 수행한다.
1부터 자기자신(N)까지의 모든 수를 대상으로 "N%(1...N)" 을 수행하지 않고, sqrt(N) 까지만 수행한다. 약수가 있다면 하나는 작은 수이고 다른 하나는 큰 수일텐데, 작은 수는 아무리 커도 sqrt(N) 보다는 작다. sqrt(N)*sqrt(N) = N 이므로 sqrt(N) 까지만 반복한다.
위의 조건에 따라 % 연산 결과가 0 이 되는 경우가 하나라도 발생하면 소수가 아니므로 그 상태에서 break; 를 수행
위의 조건을 따라 프로그램하면 다음과 같은 코드가 된다. (자바 코드)
package com.javalex.day3_1_primenumber;
public class PrimeNumberMake2 {
public static void primeMake(long startNumber, long endNumber) {
if (startNumber<=2 && endNumber >= 2) System.out.println(2 + "는 소수입니다");
if (startNumber<=3 && endNumber >= 3) System.out.println(3 + "는 소수입니다");
long modifiedNumber = 5;
if (startNumber > 5 ) modifiedNumber = startNumber;
for (long i = modifiedNumber; i<=endNumber; i++) {
boolean priNum = true;
if ((i%2==0)||(i%3==0)) priNum = false;
else {
for (int j=6; j<=(int)Math.sqrt(i)+1; j=j+6 ) {
if ((i%(j-1)==0)||(i%(j+1)==0)) { priNum = false; break; }
}
}
if (priNum==true) {
System.out.println(i+ "는 소수입니다");
}
}
}
}
아래는 위의 알고리즘이 적용되지 않은 소수 구하는 코드다. N 이 소수인것을 알기 위해 2 부터 N-1 까지 모두 나눠보고 0 으로 나누어서 떨어지는지를 검사한다. 보통 for 문을 배우면서 소수를 구하는 프로그램을 짜라고 시켜보면 이런식의 프로그램을 짠다.
package com.javalex.day3_1_primenumber;
public class PrimeNumberMake0 {
public static void primeMake(long startNumber, long endNumber) {
if (startNumber<=2 && endNumber >= 2) System.out.println(2 + "는 소수입니다");
if (startNumber<=3 && endNumber >= 3) System.out.println(3 + "는 소수입니다");
long modifiedNumber = 4;
if (startNumber > 4 ) modifiedNumber = startNumber;
for (long i = modifiedNumber ; i<endNumber; i++) {
int priNum = 0;
for (int j=2; j<i; j++ ) {
if (i%j==0) priNum++;
}
if (priNum==0) System.out.println(i+ "는 소수입니다");
}
}
}
이 두개의 코드를 돌려서 걸리는 시간을 확인해 보았다. 이때 사용한 소스는 다음과 같다.
package com.javalex.day3_1_primenumber;
public class MainPrime {
public static void main(String[] args) {
long sNum = 100_000_000L;
long eNum = 100_000_100L;
long startTime;
startTime = System.currentTimeMillis();
PrimeNumberMake0.primeMake(sNum, eNum);
System.out.println((System.currentTimeMillis()-startTime)+"ms");
startTime = System.currentTimeMillis();
PrimeNumberMake2.primeMake(sNum, eNum);
System.out.println((System.currentTimeMillis()-startTime)+"ms");
}
}
결과는 다음과 같다.
100000007는 소수입니다
100000037는 소수입니다
100000039는 소수입니다
100000049는 소수입니다
100000073는 소수입니다
100000081는 소수입니다
194011ms
100000007는 소수입니다
100000037는 소수입니다
100000039는 소수입니다
100000049는 소수입니다
100000073는 소수입니다
100000081는 소수입니다
3ms
아무런 생각없이 그냥 짠 코드의 실행시간은 194초가 걸렸다. 내 PC 의 CPU 가 i3 라서 더 느리게 나왔다. 아마도 PC 성능이 좋으면 이보다는 조금 빨리 실행이 될 것이다. 반면 2의 배수, 3의 배수를 제외하고 6k+-1 의 항목만 검사하면서 2부터 N 까지가 아닌 
194초 VS 0.003초
저 차이가 바로 프로그램에 수학과 생각이 들어가야 하는 이유다.
