1.4 소수 알고리즘

소수 판별

1) 2~n-1까지 나눠서 나머지가 0이 된것이 있는지 알아본다.

2) 2~sqrt(n)까지 나눠서 나머지가 0이 된것이 있는지 알아본다.

 

n이라는 정수까지 소수 구하기

1) 에라토스테네스의 체를 이용하여 구한다.

 

소수판별

1) 2~n-1까지 나눠서 나머지가 0이 된것이 있는지 알아본다. (O(N))

#include <iostream>

using namespace std;

bool is_prime(int num){
	for(int i=2; i<num; i++){
		if(num%i==0){
			return false;
		}
	}
	return true;
}
int main(){
	int num=28;
	cout<<is_prime(num)<<endl;

	num=13;
	cout<<is_prime(num)<<endl;
	system("pause");
	return 0;
}

0
1

 

2) 2~sqrt(n)까지 나눠서 나머지가 0이 된것이 있는지 알아본다.(O(N^(1/2)))

#include <iostream>
#include <math.h>
using namespace std;

bool is_prime(int num){

	for(int i=2; i<=(int)sqrt((double)num); i++){
		if(num%i==0){
			return false;
		}
	}
	return true;
}
int main(){
	int num=28;
	cout<<is_prime(num)<<endl;

	num=13;
	cout<<is_prime(num)<<endl;
	system("pause");
	return 0;
}

0
1

 

n이라는 정수까지 모든 소수 구하기

1) 에라토스테네스의 체를 이용하여 구한다.

#include <iostream>
#include <vector>
using namespace std;

int main(){
	int num = 28;
	vector<int> vc;
	for(int i=0; i<=num; i++){
		vc.push_back(0);
	}
	vc[0] = 1;
	vc[1] = 1;
	for(int i=2; i<=num; i++){
		if(vc[i]==1){
			continue;
		}
		int j=i; // i를 기점으로 해서
		while((j+=i)<=num){
			vc[j]=1;
		}

	}

	for(int i=0; i<=num; i++){
		if(vc[i]==0){
			cout<<i<<" ";
		}
	}
	cout<<endl;
	system("pause");
	return 0;
}

2 3 5 7 11 13 17 19 23