소수 알고리즘

소개글

소수 알고리즘에 대한 보고서 자료입니다.

목차

1.문제정의

2.알고리즘 설명

3.프로그램

4.결과

5.결과분석

6.토의

7.개선된 소수코드

본문내용

rue;
// bool타입을 true로 초기화.
int j = 3, p = 0;
// j를 3~num-1까지 반복해서 i를 나누기 위해.
// p는 i의 제곱근보다 작은소수로 나누기위해.
if(i%2 == 0) // 짝수 제외.
{
b_divide = false;
}
while(b_divide == true && j <= sqrt(i) && arr[p] <= sqrt(i))
{
if(i%j == 0 || i%arr[p] == 0)
// i가 한 번이라도 나누어지거나
// arr[p]로 나누어지면 소수가 아님.
{
b_divide = false;
}
j += 2;// 홀수로 나누어지게 한다.
p++; //arr의 인덱스가 증가.
process_num++;
}
if( b_divide == true)
// 한 번도 나누어 떨어지지 않았으면
// 소수 i를 출력.
{
cout << "소수는 " << i << ",";
arr[0] = 3;// 첫번째 인덱스에 3를 넣는다.
arr[k] = i; // 소수를 배열에 저장.
k++; // 인덱스를 증가.
}
}
cout << "\n수행 횟수는 " << process_num << "번 입니다.\n";
delete[] arr; //사용한 메모리 해제
arr = NULL;
return 0;
}
4. 결과
◆ A1
○ num = 100 일때.
○ num = 1000 일때.
○ num = 10000 일때.
◆ A2
○ num = 100 일때.
○ num = 1000 일때.
○ num = 10000 일때.
◆ A3
○ num = 100 일때.
○ num = 1000 일때.
○ num = 10000 일때.
◆ A4
○ num = 100 일때.
○ num = 1000 일때.
○ num = 10000 일때.
◆ A5
○ num = 100 일때.
○ num = 1000 일때.
○ num = 10000 일때.
5. 결과 분석
알고리즘
나머지 연산 수행 횟수
num = 100
num = 1000
num 10000
A1
5,049
500,499
50,004,999
A2
1,133
78,022
57,752,23
A3
530
38,678
2,884,498
A4
87
2351
55,958
A5
84
1804
33,756
A1/A5
50.1
277.4
1,481.4
=> A1부터 A5부터 알고리즘을 개선해 나가면서 수행해 본 결과
num = 100일 때, 수행 횟수는 차이는 A1는 A5보다 50.1배.
num = 1000일 때, 수행 횟수는 차이는 A1는 A5보다 277.4배.
num = 10000일 때, 수행 횟수는 차이는 A1는 A5보다 1,481.4배가
차이가 나는 것을 알수 있었습니다.
6. 토의
=> 알고리즘을 개선하기 위해서 소수 구하는 법칙을 알게 되었습니다.
에라토스테네스의 체, 페르마 소수, 메르센 소수, 쌍둥이 소수등
을 알게 되었지만 프로그램에서는 정확한 값을 출력해야함으로
이 법칙들은 정확한 소수들이 나오지 않고 일부만 증명되어서
이 소수 법칙들을 사용하지 못했다.
그래서 조금이나마 수행 횟수를 줄이기 위해, 2의 배수 즉 짝수를 제외
시킨거처럼 소수인 3,5,7의 배수들을 줄여서 수행 횟수를 조금이나마
빠르게 할 수 있었다.만일 더 많은 소수의 배수을 제외 시키면 프로그램
수행 횟수가 줄어들 수 있겠으나 그러면 소스를 보기 힘들어져
그렇게 하지는 않았다.
개선된 알고리즘을 뒷장에 첨부하였습니다.
◆ A6
#include
#include
using namespace std;
int main()
{
int process_num = 0, num,k = 1;
// process_num => 수행 횟수를 계산.
// num => 입력할 숫자 변수
cout << "숫자를 입력하시오 : "; //입력 부분.
cin >> num ;
int* arr = new int[num];
//num만큼의 메모리를 할당한다.
if(num >= 2)//소수인 2출력
{
cout << "소수는 2,";
}
if(num >=3)//소수인 3출력
{
cout << "소수는 3,";
}
if(num >= 5)//소수인 5출력
{
cout << "소수는 5,";
}
if(num >=7)//소수인 7출력
{
cout << "소수는 7,";
}
for(int i = 8; i <= num; ++i)
// 8~num까지 증가
{
bool b_divide = true;
// bool타입을 true로 초기화.
int j = 3, p = 0;
// j를 3~num-1까지 반복해서 i를 나누기 위해.
// p는 i의 제곱근보다 작은소수로 나누기위해.
if(i%2 == 0) // 짝수 제외.
{
b_divide = false;
}
if(i%3 == 0) // 3의 배수 제외
{
b_divide = false;
}
if(i%5 == 0) // 5의 배수 제외
{
b_divide = false;
}
if(i%7 == 0) // 7의 배수 제외
{
b_divide = false;
}
while(b_divide == true && j <= sqrt(i) && arr[p] <= sqrt(i))
{
if(i%j == 0 || i%arr[p] == 0)
// i가 한 번이라도 나누어지거나
// arr[p]로 나누어지면 소수가 아님.
{
b_divide = false;
}
j += 2;// 홀수로 나누어지게 한다.
p++; //arr의 인덱스가 증가.
process_num++;
}
if( b_divide == true)
// 한 번도 나누어 떨어지지 않았으면
// 소수 i를 출력.
{
cout << "소수는 " << i << ",";
arr[0] = 3;// 첫번째 인덱스에 3를 넣는다.
arr[k] = i; // 소수를 배열에 저장.
k++; // 인덱스를 증가.
}
}
cout << "\n수행 횟수는 " << process_num << "번 입니다.\n";
delete[] arr; //사용한 메모리 해제
arr = NULL;
return 0;
}
◆ 결과
○ num = 100 일때.
○ num = 1000 일때.
○ num = 10000 일때.

키워드

소수,   알고리즘,   프로그램,   소스