[C+] 오토마타 이용한 소수구하기 - 소스 및 실행화면

소개

[C+] 오토마타 이용한 소수구하기 - 소스 및 실행화면

목차

알고리즘 1 : 소스 및 실행화면
알고리즘 2 : 소스 및 실행화면
알고리즘 3 : 소스 및 실행화면
알고리즘 4 : 소스 및 실행화면
결론

본문내용

1번 알고리즘은 기본적인 것으로써 소수를 구하는 알고리즘이라 특별 한 것이 없는 소스이다. 2번 알고리즘부터 개선이 되는데

2번부터는 1로 나누어 볼 필요가 없고 자기자신을 나누어 볼 필요도 없기 때문에 2부터 i-1까지 나누어 소수를 구해보았다. 그리고 while문으로 flag를 사용하여 조건에 만족할때만 for문을 돌수 있도록 변경하였다.

3번 알고리즘은 짝수로 나누어 볼 필요가 없기 때문에 I를 홀수로 증가시켰고 또 처음에 2로도 나누어 볼 필요가 없고 2로 나누면 바깥 반복문에서 if문으로 2일때는 1을 증가시키고 2가 아닌 경우 2씩 증가시켜 홀수로 만들어주어야한다 그렇게 하면 필요없이 소스가 길어지기 때문에 I를 3부터 나눠주었다 나머지 4번 5번 알고리즘도 그런식으로 I를 3번부터 시작해주었다.

4번 알고리즘은 sqrt를 사용하는데 이 함수는 math.h를 필요로 한다. 역시 3번알고리즘처럼 바깥도 홀수로 나누어 주었고 안쪽 반복문은 sqrt(i)로 나누어 줌으로써 소수를 구할 때 필요없는 나머지 연산횟수를 줄여줌으로써 더 개선되었다.

5번 알고리즘은 4번해서 구한 소수를 배열에 저장하여 배열에 저장된 0번부터 count를 늘려줌으로써 배열에 저장된 소수를 I에 나누어 볼 수 있도록 하였고 그 결과 4번보다 총 3회가 줄어든 84번의 결과가 나왔다. 이때 주의해야 할 것이 count 변수였는데 data[count]이런 식으로 해주었는데 count를 증가 시키는 count++을 어디에 두어야 할지 잘 생각해야하며 다른 조건들와 헷갈려 자칫 count+=2를 할지 모르니 주의해야했다. 데이터가 저장되어있는 것으로 나누는 것이니 count는 1씩 증가시켜야 하는데 조건문이 포함되어 있다 보니 count++이 위치해야할 자리가 처음에 한눈에 보이지 않아 많이 고민했었다.

참고자료

· 없음