C++ 소수 ( 쉽게 구하는 방법 )

1. 루트를 이용해서 구하기 

결론 부터 이야기하면 n 의 제곱근 까지만 조사해 보면 된다. 

ex) 

for(int i =0; i< sqrt(x) ;i++)

if( number % i ==0)

break;

특정 수 n 이 있다고 생각해 보자 

n = a* b 로 된 합성수이다. 

n 의 제곱근을 n' 이라고 하면 ( 25의 제곱근은 ? => x^2 = 25 가 되는 x 는 무엇인가? 5가 된다 ) 

a 가 n'보다 크거나 같다보면 ( a >= n' ) b는 n' 보다 작거나 같다 ( b <=n') 

왜냐면 25로 생각해 보면 5*5 가 된다 그런데 1*25도 된다. 즉 무조건 하나는 제곱근 보다 작게 된다. 만약 합성수라면 제곱근 보다 작

은 수에서 나눠지게 된다. 또 다른 예로는 16으로 하면 4*4 있고 2*8 이 있다. 제곱근인 4보다는 2는 작고 8은 크게 된다. 즉 4까지만 

조사 하면 2에서 나눠지게 되기 때문에 소수 판별이 된다. 

코드

#include <iostream>

#include <math.h>

#include <vector>

using namespace std;

void findPrim(int first,int second)

{

int count=0;

bool check = true;

for(int i=first ; i <= second ;i++)

{

for(int j=3;j<= sqrt(i);j+=2)

{

if(i%j==0 || i% 2 ==0)

{

check = false;

break;

}

}

if((check && i!=1) || second == 2)

{

count++;

}

check = true;

}

cout<< count<<endl;

}

int main()

{

vector<int> v;

v.push_back(10);

int number[123456];

int index =0;

while(1){

int num;

cin>>num;

if(num ==0)

{

break;

}else{

number[index++]=num;

}

}

for(int i =0;i<index;i++)

findPrim(number[i]+1,2*number[i]);

return 0;

}

----------------------------------------]------

2. 에라스토테네스의 체를 이용하여 소수의 범위