소수판별법 에라테네스체

소수를 판별하는 방법은 2가지다.

첫번째는 입력받은 값을 2부터 입력받은값까지 다 나눠보고 나머지가 0인게 뜨면
그새끼는 소수가 아닌거임. 이걸로 했을땐 시간복잡도 값이 O(n)이 됨.

두번째는 에라테네스체를 사용하는거다.
소수를 판별할때 젤 먼저 보게 되는게 이 새끼가 2의 배수인가? 아니면 3의 배수인가다.
그 담으로는 n에 루트를 취했을때 루트n에 대해서 대칭이 된다.
이때 시간복잡도 값은 O(루트n)이 된다.

1.첫번째 방식으로 풀어보자.

#include<stdio.h>
#include<stdlib.h>

int main(){
        int n;
        int i;
        scanf("%d",&n);
        for(i=2;i<n;i++){
                if(n%i==0){
                puts("합성수");
                return 0;
                   }
                else{
                puts("소수");
                return 0;
                   }
                }
        return EXIT_SUCCESS;
        }

2.두번째 방식

isPrime 함수 정의후 사용하기.(말그대로 is Prime? 이거임)

#include<stdio.h>

#include<stdlib.h>

#include<math.h>

int isPrime(int n);

double sqrt(double n);

int main(){

        int n;

        scanf("%d",&n);

        if(isPrime(n)!=0){

                puts("소수");

         }

        else{

                puts("합성수");

        }

        return EXIT_SUCCESS;

}

int isPrime(int n){

        int i;

        int x=(int)sqrt(n);

        if(n%2==0){

                return n==2;

        }

        if(n%3==0){

                return n==3;

        }

        for(i=5;i<=x;i++){

                if(n%i==0){

                 return 0;

                }

        }

        return n!=1;

}