루덴스코드 Blog


처음코딩을 시작한 사람들을 위한 베이비스텝과정입니다.

잘 몰라도 괜찮습니다. 혼자서 못하는 건 당연합니다. 누군가 도와주지 않으면 일어설 수 없는 베이비가 처음 걸음을 걸을때의 기쁨과 감격을 다시 한번 느껴봅시다.

혼자서 힘들면 누군가와 함께 일어서는 연습을 합시다. 

베이비스텝, 시작합니다.


2017년 12월 29일 부터 30일, 금요일과 토요일 무박2일로 베이비스텝을 진행합니다.

신청자를 받습니다. 6명 이상이면 진행하겠습니다. 참가 신청은 12월 9일부터 16일까지 받겠습니다. 양식링크는 이곳에 게제합니다. 세부내역은 12월 9일에 공지하겠습니다.


Comment +0

소수구하는 알고리즘


예전에 파이썬으로 했던 소수 알고리즘이다.

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 까지가 아닌 까지 검사하면고, 소수가 아니면 바로 break 를 써서 빠진 결과는 3ms 가 나왔다.


194초 VS 0.003


저 차이가 바로 프로그램에 수학과 생각이 들어가야 하는 이유다.

Comment +0


자바 공부하시는 분들 참고하세요.

소수구하는 알고리즘을 이용한 클래스 강의 자료입니다.

이클립스에서 실행하세요.


///////////////////////////////////////////

// PrimeNumberMake.java

///////////////////////////////////////////


package com.javastudy.primesecure;

import java.util.Random;


public class PrimeNumberMake {

private long passwordElement1; 

private long passwordElement2; 

private long passMultiValue;


public PrimeNumberMake() {

Random randNum = new Random();

passwordElement1 = primeMake(1_234_567_890L+randNum.nextInt(100_000_000));

passwordElement2 = primeMake(2_345_678_901L+randNum.nextInt(100_000_000));

passMultiValue = passwordElement1 * passwordElement2;

}

public long getPasswordElement1() {

return passwordElement1;

}


public long getPasswordElement2() {

return passwordElement2;

}


public long getPassMultiValue() {

return passMultiValue;

}


public long primeMake(long startNumber) {

long i = startNumber;

boolean priNum = false;

while(!priNum) {

i++;

priNum = true;

if ((i%2==0)||(i%3==0)) priNum = false;

else {

for (int j=6; j<Math.sqrt(i); j=j+6) {

if((i%(j-1)==0)||(i%(j+1)==0)) { 

priNum=false; 

break;

}

}

}

}

return i;

}

}


///////////////////////////////////////////

// MainPrime.java

///////////////////////////////////////////


package com.javastudy.primesecure;


public class MainPrime {


public static void main(String[] args) {

PrimeNumberMake pswd = new PrimeNumberMake();

System.out.println("첫번째 소수값 : "+pswd.getPasswordElement1());

System.out.println("두번째 소수값 : "+pswd.getPasswordElement2());

System.out.println("두소수의 곱   : "+pswd.getPassMultiValue());

}

}



Comment +0