소수판별

소수관련된 문제를 풀다가 소수구하기 프로그램을 짜보았다.

여러가지 방법이있는것 같다. 

지금 내가 짠 것은 가장 기본적으로 생각할수있는 코드인것같다.

2부터 입력받은 숫자전의 숫자까지 나누어 본후

만약 나머지가 0이 나오지않으면

카운트를 올리고,

카운트가 모두돌아간경우(입력받은값-2 (0과1제외)) 

소수라고 출력해준다.

#include<iostream>
using namespace std;
int main()
{
    ios::sync_with_stdio(false);
    int n;
    int a=0;
    
    cin>>n;
 
    for(int i=2;i<n;i++)
    {
        if(n%i!=0)
        {
            a=a+1;
        }
    }
 
    if(a==n-2)
    {
        cout<<"소수가 맞음"<<endl;
    }
    else
    {
        cout<<"소수가아님"<<endl;
    }
 
 
}

이것다음으로는 

count를 세는것이아닌

true false처럼 한번이라도 나누어떨어질때 변수의 값을 바꾸어 판별하는 방법이다.

#include<iostream>
using namespace std;
int main()
{
    ios::sync_with_stdio(false);
    int n;
    int a=1;
    
    cin>>n;
 
    for(int i=2;i<n;i++)
    {
        if(n%i==0)
        {
            a=0;
        }
    }
 
    if(a==0)
    {
        cout<<"소수가 아님"<<endl;
    }
    else
    {
        cout<<"소수가 맞음"<<endl;
    }
 
 
}

여기서 조금더 좋은 프로그램은, for문 안의 if문에 조건만족시 break문을 넣어주어 소수가아니라는것을 알았을때 더이상 돌아가지 않게 하는것이다.

#include<iostream>
using namespace std;
int main()
{
    ios::sync_with_stdio(false);
    int n;
    int a=1;
    
    cin>>n;
 
    for(int i=2;i<n;i++)
    {
        if(n%i==0)
        {
            a=0;
            break;
        }
    }
 
    if(a==0)
    {
        cout<<"소수가 아님"<<endl;
    }
    else
    {
        cout<<"소수가 맞음"<<endl;
    }
 
 
}

그러던중 나는 더 놀라고말았다...

더좋은 방법?........... 알고리즘? 을 찾아버렸다 바로 에라토스테네스의 체 라는것이다!

2부터 입력받은 숫자까지 모두 배열에 담고,

소수가아닌것들을 모두 0으로 바꾸어 버린다.

(2부터 입력받은수까지 배수들을 0으로바꾼다)

ex 2의배수를 지운다(2를제외한).  4 6 8 ...

   3의배수를 지운다(3을제외한).  6 9 12 ...

0이아닌수는 모두 소수이다.

그래서 아래소스는 입력받은 숫자보다 작은 소수를 나오게 하였다.

#include<iostream>
using namespace std;
int main()
{
    ios::sync_with_stdio(false);
    int n;
    cin>>n;
 
    int *arr=new int[n];
 
    for(int i=2;i<=n;i++)
    {
        arr[i]=i;
    }
 
    for(int i=2;i<n;i++)
    {
        for(int j=2;j<n;j++)
        {
        
            if(arr[j]!=i && arr[j]%i==0)
            {
                arr[j]=0;
            }
 
        }
    }
 
    for(int i=2;i<n;i++)
    {
        if(arr[i]!=0)
        {
             cout<<arr[i]<<endl;
 
        }
    }
 
 
    
}