Prime
Learning Goals
- for 루프 사용 연습
- modulo(나머지) 사용
- Boolean 함수 만들기
Background
소수는 1보다 큰 정수로 정의되며, 인수는 1과 자기 자신뿐입니다. 따라서 3은 약수 1과 3뿐이므로 소수이고, 4는 2×2의 곱이므로 소수가 아닌 합성수입니다. 이 실습에서는 사용자가 지정한 범위의 모든 소수를 생성하는 알고리즘을 작성합니다.
Demo
Getting Started
- GitHub 계정을 사용하여 cs50.dev에 로그인합니다.
- 터미널 창 내부를 클릭하고 cd를 실행합니다.
- 이제 cd prime 을 실행해 보세요.
- 그런 다음 wget https://cdn.cs50.net/2022/fall/labs/1/prime.c 를 터미널에 복사하여 붙여넣어 이 실습의 배포 코드를 다운로드하세요.
- 숫자가 소수인지 테스트하고, 소수이면 true를 반환하고, 그렇지 않으면 false를 반환하는 Boolean 함수인 prime을 완성해야 합니다.
Implementation Details
숫자가 소수인지 확인하는 가장 쉬운 방법은 숫자 자체를 포함하지 않고 2부터 모든 숫자로 나누는 것입니다. 어떤 숫자가 나머지 없이 나누어지면 그 숫자는 소수가 아닙니다.
배포 코드의 주요 기능에는 사용자가 지정한 범위(양쪽 끝 포함)를 반복하는 for 루프가 포함되어 있습니다. 예를 들어 사용자가 최소값에 1을 입력하고 최대값에 100을 입력하면 for 루프는 1부터 100까지 각 숫자를 테스트합니다. 이러한 숫자 각각은 숫자가 소수인지 여부에 따라 true 또는 false를 반환하도록 구현할 Prime 함수에 전달됩니다.
생각해보기
숫자가 자신보다 작은 2와 1 사이의 모든 숫자로 나누어지는지 확인하는 것보다 소수 찾기 알고리즘을 더 효율적으로 만들 수 있습니까? 소수를 생성하는 다른 방법을 생각해 볼 수 있나요?
나의 풀이
#include <cs50.h>
#include <stdio.h>
bool prime(int number);
int main(void)
{
int min;
do
{
min = get_int("Minimum: ");
}
while (min < 1);
int max;
do
{
max = get_int("Maximum: ");
}
while (min >= max);
int count = 0;
for (int i = min; i <= max; i++)
{
if (prime(i)) // if i is prime
{
count ++;
printf("%i\n", i); // print i
}
}
printf("Count: %i\n", count); // count
}
bool prime(int number)
{
// TODO
int zeroModule = 0;
for (int i = 2; i < number; i++)
{
int module = number % i;
if (module == 0)
{
zeroModule++;
break;
}
}
if (number == 1 || zeroModule > 0)
{
return false;
}
else if (number == 2)
{
return true;
}
else {
return true;
}
}
처음엔 단순하게 생각해서 2로 나누어지지만 않으면 되겠네! 했으나
1 ~ 100 사이의 소수가 51개가 되는 마법이..
2 이외에도 약수가 될 수 있는 숫자는 많았다. 2, 3, 5.. 등등
정수 N를 2부터 시작해서 N-1 숫자까지 값으로 for 루프를 돌려 나눠 나머지를 구한 후 그 나머지들 중 0이 있다면 그 수는 소수가 아니다.
내가 작성한 bool함수를 살펴보면, 우선 입력 단계에서 0 이후의 숫자부터 입력받을 수 있으므로,
1과 2의 조건을 걸어주고, zeroModule(나머지가0)이라는 정수형 변수를 설정한 후 for문으로 각 number가 2부터 number-1 숫자까지 나눈 후 나머지가 0이 라면 zeroModule를 카운트업하고 해당 for문은 break.
따라서 zeroModule이 0보다 크면 해당 숫자는 소수가 아니므로 false를 그 외의 모든 숫자는 소수가 될테니 true를 리턴해줬다.
이 소수구하기 알고리즘은 어떤 알고리즘을 선택하느냐에 따라 시간복잡도가 달라진다고 한다.
그 중 에라토스테네스의 체의 원리를 사용한 알고리즘이 가장 시간복잡도가 낮다.
에라토스테네스의 체
- 1부터 n까지의 표를 만들고 1을 제외한다.
- 제외되지 않은 가장 작은 수를 찾는다. 해당 수는 소수이다.
- 해당 수의 배수들을 모두 지운다. -> 반복
