소수 찾기

✅point

🔺어떤 정수 n이 소수일 조건

1.➡️2~n-1까지의 어떤 정수로도 나누어 떨어지지 않는다.

2.➡️2~n-1까지의 어떤 소수로도 나누어 떨어지지 않는다. (어떤 소수로 나누어 떨어진다는 건 그 소수의 배수(어떤 합성수)로도 나누어 떨어진다는 거니까 소수만 고려하면 더 효율적)

3.➡️n제곱근(루트n)이하의 어떤 소수로도 나누어 떨어지지 않는다. (n의 약수는 루트n을 기점으로 반반 대칭이므로 루트n이하 범위의 소수만 고려해 나눠보면 더 효율적)

=>3번이 가장 개선된 알고리즘이다. 연산 횟수가 가장 적음

 

✅실습2-11(개선된 알고리즘)

/*1000이하의 소수 구하기*/
#include <stdio.h>

int main()
{
  int i, n;
  int prime[500]; //구한 소수들 저장할 배열. (*크기 500 설정 이유: 1000이하 소수는 무조건 500개 이하임. 2의 배수 제외하면.)
  int ptr = 0;  //이미 얻은 소수의 개수
  unsigned long counter;  //연산 횟수(곱셈&나눗셈)

  prime[ptr++] = 2; //prime[0]에 2저장
  prime[ptr++] = 3; //prime[1]에 3 저장

  for(n=5; n<=1000; n+=2)  //5~1000까지 홀수들만 소수판별
  {
    int flag = 0; //소수면 flag=0, 합성수면 flag=1
    for(i=1; counter++, prime[i]*prime[i]<=n; i++)  //루트n이하의 prime[i]만. 이때 곱셈연산 횟수 count
    {
      counter++;  //나눗셈 연산 count
      if(n % prime[i] == 0) //루트n이하의 소수로 나눠지면
      {
        flag = 1; //합성수
        break;  //안쪽 for문 break
      }
    }
    if(!flag) //flag==0이면(소수)
    {
      prime[ptr++] = n; //소수 저장
    }
  }

  //소수 출력
  for(i = 0; i<ptr; i++)
  {
    printf("%d ", prime[i]);
  }

  printf("\n총 연산횟수: %lu\n", counter);

  return 0;
}