j가 2부터 i에 도달할때까지 1씩 더하면서 i와 나누어 떨어지면 (1과 자기 자신을 제외한 인수가 있으므로) 소수가 아님.
위 연산을 반복해서 0~N 까지 소수의 개수를 하나하나 판단하여 카운팅한다.
각 범위를 계산하며 시간을 측정해본 결과는 아래 표와 같다.
#include<stdio.h>
#include<math.h>
int main() {
int i, j, cnt=0, flag=1;
unsigned int min, max;
// 범위 입력
printf("min : ");
scanf_s("%d", &min);
printf("max : ");
scanf_s("%d", &max);
// 2보다 작은 최소 범위가 입력되면 2로 고정
if (min < 2) min = 2;
printf("입력 받은 범위 내의 소수");
// i가 입력받은 최소 범위부터 최대 범위까지 반복
for (i = min; i < max; i++)
{
flag = 1; // 현재수가 소수라고 가정하고 시작
// j는 2부터 현재의 i 전까지 증가
for (j = 2; j < i; j++)
{
// i와 j를 나눈 나머지가 존재하면 소수가 아님
if (i % j == 0)
{
flag = 0; // flag가 0이면 현재 수(i)는 소수가 아님
break; // 더 이상 j로 나누어 줄 필요가 없으므로 탈출
}
}
// 위에서 판단된 결과가 소수이면(0이 아니면)
if (flag)
{
cnt++; // 개수를 증가시킴 (입력 받은 범위 내의 소수 개수)
printf("%d\t", i); // 출력
if (cnt % 5 == 0)
{
printf("\n"); // 5개 단위로 끊음
}
}
}
printf("\n%d ~ %d 사이의 소수 개수 : %d개\n", min, max, cnt);
return 0;
}
범위
개수
시간(s)
2~100
25
0.000s
2~1000
168
0.001s
2~10000
1229
0.028s
2~100000
9592
0.973s
2~1000000
78498
119.606s
2~10000000
-
-
코드 2 - i (2 ~ N)를 j (2 ~ i / j)로 나누기
현재 수 i가 2의 배수일 경우 i/2 * 2 = i, 3의 배수일 경우 i/3 * 3 = i, 5와 7의 배수일 경우는 i/5 * 5 = i, i/7 * 7 = i 가 성립한다. (4, 6등은 2와 3의 배수이므로 해당 범위에 포함된다.)
위 공식을 일반화시키면 아래와 같고,
i/n * n = i
여기서 i의 소인수는 j와 i/j의 곱셈이므로 j는 i/j보다 클 수 없다는 가설을 적용하여 코드를 작성했다.
(수가 커질수록 더 많은 범위의 계산이 생략되므로 속도가 빨라짐)
아래 표를 보면 코드1의 방식보다 좀 더 개선된 걸 볼 수 있다.
#include<stdio.h>
#include<math.h>
#include<time.h>
void test(int min, int max)
{
clock_t start, end;
float res;
int i, j, cnt = 0, flag;
start = clock();
for (i = min; i < max; i++)
{
flag = 1;
// 기존과 달라진 부분, j로 확인 하는 범위를 i와 현재 j의 나눈 몫까지로 줄였음
for (j = 2; j <= (int)(i / j); j++)
{
if (i%j == 0)
{
flag = 0;
break;
}
}
if (flag)
{
cnt++;
}
}
end = clock();
res = (float)(end - start) / CLOCKS_PER_SEC;
printf("%d~%d : %d개\t%.3fms\n", min, max, cnt, res);
}
int main() {
int arr[] = {100, 1000, 10000, 100000, 1000000, 10000000, 1000000000};
for (int i = 0; i < (int)(sizeof(arr) / sizeof(int)); i++)
{
test(2, arr[i]);
}
return 0;
}
범위
개수
시간(s)
2~100
25
0.000s
2~1000
168
0.000s
2~10000
1229
0.001s
2~100000
9592
0.028s
2~1000000
78498
0.359s
2~10000000
664579
7.392s
2~100000000
5761455
202.174s
2~1000000000
50847534
5087.694s
2~10000000000
-
-
코드 3 - 에라토스테네스의 체
에라토스테네스의 체를 활용하여 미리 계산된 소수 여부 테이블을 참조하는 방식으로 개수 확인한다.
작은 범위에서는 위의 알고리즘 들과 비슷하거나 느리지만 큰 수의 범위로 가면 훨씬 빠른걸 볼 수 있다.
#include <iostream>
using namespace std;
typedef unsigned long long ll;
/*
* input : int m
* output : 1부터 m까지의 소수 여부를 sizeof(bool) * (m+1)크기의 bool * 형태로 반환한다.
* 사용 시 반환된 bool array에 해당 자연수를 조회하면 소수 여부를 알 수 있다.
*/
bool *Sieve_of_Eratosthenes(ll m) {
bool* arr = new bool[m + 1];
memset(arr, 1, sizeof(bool) * (m+1));
arr[0] = false;
arr[0] = false;
for (ll i = 2; i < m + 1; i++) {
if (arr[i] == true) {
for (ll j = i * 2; j < m + 1; j += i) {
arr[j] = false;
}
}
}
return arr;
}
int main() {
clock_t start, end;
ll N, M;
ll sum=0;
start = clock();
cin >> N >> M;
bool* arr = Sieve_of_Eratosthenes(M);
for (ll i = N; i <= M; i++) {
if (arr[i]) {
sum++;
}
}
end = clock();
float res = (float)(end - start) / CLOCKS_PER_SEC;
cout << "" << N << " " << M << " " << sum << ", " << res << "ms" << endl;
return 0;
}
범위
개수
시간(s)
2~100
25
7.149
2~1000
168
9.231
2~10000
1229
14.213
...
-
-
2~100000000
5761455
53.387
2~1000000000
50847534
23.744
2~10000000000
455052511
252.08
2~100000000000
-
-
참고
계산 범위의 조절로 100만에서 1억으로 향상되었지만 여전히 큰 수를 처리하기엔 어려움
에라토스테네스의 체를 활용할 경우 테이블 생성으로 인해 작은 수 범위에서는 더 오래걸리지만, 큰 수에서는 훨씬 적은 시간이 걸림. (1억에서 100억 단위로 향상됨)
#include "stdafx.h"
#include <ctype.h>
#include <math.h>
int gcd(int a, int b);
int RSA(int n, int m, int d);
int main(){
// 키 생성
//int p = 13, q = 37;
//int p = 11, q = 13;
int p = 17, q = 13;
int n, e, d, f;
n = p * q;
f = (p-1) * (q-1);
// e 결정
for (int i = 2; i < f; i++) {
// 서로소 판단
if (gcd(p - 1, i) == 1 && gcd(q - 1, i) == 1) {
e = i;
break;
}
}
//d 결정
for (int i = 1; i < n; i++) {
if ((1 + f * i) % e == 0) {
d = (1 + f * i) / e;
break;
}
}
// 소수에 따라 자동 계산된 변수 값
printf("p\tq\tn\te\td\tf\n");
printf("%d\t%d\t%d\t%d\t%d\t%d\n\n", p, q, n, e, d, f);
// 암호화
int msg = 'b';
printf("msg : %c\n", msg);
int c = RSA(n, msg, e);
printf("c : %c\n", c);
// 복호화
int msg2 = RSA(n, c, d);
printf("msg : %c\n", msg2);
return 0;
}
// 암복호화를 위한 모듈로 연산을 수행 (n, d는 공개키/ 개인키, m은 메시지)
int RSA(int n, int m, int d) {
int bin1[10] = { 0, };
int tmp, j = 1;
unsigned long long x_tmp = 1;
int x[10]; // m^2^0~9 mod n
// 거듭 제곱법 구현을 위한 값 미리 저장
x[0] = (unsigned long long)pow(m, 1) % n;
for (int i = 1; i < 10; i++) {
x[i] = (x[i - 1] * x[i - 1]) % n;
}
// 지수를 이진수로 변환 (구현 편의성을 위해 그냥 역으로 넣음)
for (int i = 0; d > 0; i++) {
tmp = d % 2;
d /= 2;
bin1[i] = tmp;
}
// 이진수가 1일 떄만 미리 계산된 값 곱셈
for (int i = 0; i < 10; i++) {
if (bin1[i] == 1) {
x_tmp *= x[i];
}
}
return x_tmp % n; // 곱셈 합을 모듈로해서 반환
}
// 최대 공약수
int gcd(int a, int b) {
int tmp, n;
if (a<b) {
tmp = a;
a = b;
b = tmp;
}
while (b != 0) {
n = a % b;
a = b;
b = n;
}
return a;
}
3. 결과
4. 참고 사항
- 메르센 소수 같은 빅넘버를 처리하기엔 부적합함 (이 경우 OpenSSL 활용)
- 거듭 제곱법 구현 함수 내 배열을 10으로 고정해두었으나 배열 크기 조정으로 어느정도 큰 소수
(x_tmp 최대값, unsigned long long) 까지는 연산이 가능함.
- 문자를 하나씩 암호화 하면 같은 문자는 같은 값으로? 암호화됨. (블록 단위 암호화 필요)
ex) testtest -> abcaabca
- 자료형 크기 고려했을 때 문자를 대충 4바이트 단위까지 합쳐서 연산가능할 듯
ex) asdf -> 16진수변환 한번에 연산 등등
내용 수정
2024-01-21(일)
- 기존 코드에서 잘못된 부분을 확인하여 수정이 필요한 부분을 적어두었음
- e를 결정하는 부분에서 e와 f가 서로소인 부분이 확인 되어야 하기 때문에 기존 코드의 gcd(p - 1, i) == 1 && gcd(q - 1, i) == 1 부분이 제거 되고 아래처럼 수정되어야 함
f = (p-1) * (q-1);
// e 결정
for (int i = 2; i < f; i++) {
if (gcd(i, f) == 1) {
e = i;
break;
}
}
