byeol2ing 2018. 5. 1. 23:09
반응형


- 소수 판별법

. 소수(Prime Number)란?

1과 자기자신 이외에는 나누어 떨어지는 정수가 없는 양의정수


1. 2~N-1까지의 정수로 나누어 보는 방법 - O(N)

2. 2~Sqrt(N)까지의 정수로 나누어 보는 방법 O(N^1/2)



1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
#include<stdio.h>
#include<math.h>
 
int is_prime(int n)
{
    int i;
    for(i=2;i<n;i++){
        if(n%i == 0){
            return false;
        }
    }
    return true;
}
 
int is_prime2(int n)
{
    int i,sqrn;
    sqrn=(int)sqrt(n);
    for(i=2; i<=sqrn; i++){
        if(n%i==0){
            return false;
        }
    }
    return true;
}
cs




 - 에라토스테네스의 체

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
 
    int main(int argc, char*argv[])
    {
        if(argc<2){
            printf("Usage : prime2[integer]\n");
            return 0;
        }
 
        int n=atoi(argv[1]);
        if(n<2){
            printf("Error : n must be greater than 1\n");
            return 0;
        }
 
        int *parray;
        parray = new int [n+1];
        if(parray==0){
            printf("Error : memory allocation failed\n");
            return 0;
        }
 
        memset(parray,0,sizeof(int)*(n+1));
 
        int i,j;
        for(i=2; i<=n; i++){
            if(parray[i]==1)
                continue;
 
            j=i;
            while((j+=i)<=n){
                parray[j]=1;
            }
        }
 
        for(i=2;i<=n;i++){
            if(parray[i]==0)
                printf("%d",i);
        }
        printf("\n");
 
        delete[]parray;
        return 0;
    }
 
cs


실행결과



반응형