문제를 보고 떠오른 생각
일단 1은 소수가 아니기 때문에 제외하고 2부터 (입력받은 값-1)까지 i를 증가시키면서 입력받은 값을 i로 나눈 나머지가 0이면 소수가 아니고, 나머지가 0이 아니면 소수이므로 이를 표현하려고 함.
알고리즘
- is_prime을 처음에 1로 고정.
- i로 나눈 나머지가 0이면 소수가 아니므로 is_prime=0 이고 반복문은 빠져나올 break;를 선언해줌.
- 나머지가 0이 아니라면 소수이므로 is_prime=1일것이고, if(1)을 통해 count_number을 증가시켜줌.```
#include <stdio.h>
int main(void) {
int arr[1000] = { 0 };
int N;
int count_number = 0;
scanf("%d", &N);
for (int i = 0; i < N; i++) {
scanf("%d", &arr[i]);
//소수의 규칙을 먼저 찾기
}
for (int i = 0; i < N; i++) {
int is_prime = 1;
if (arr[i] < 2) {
is_prime = 0;
}
for (int k = 2; k < arr[i]; k++) {
if (arr[i] % k == 0) {
is_prime = 0;
break;
}
}
if (is_prime) {
count_number++;
}
}
printf("%d", count_number );
return 0;
}에라토스테네스의 체(백준 2960번)
에라토스테네스의 체 알고리즘은 여러 개의 수가 소수인지 아닌지를 판별할 때 사용하는 대표적인 알고리즘입니다. 에라토스테네스의 체는 N보다 작거나 같은 모든 소수를 찾을 때 사용할 수 있습니다. 알고리즘을 먼저 살펴보겠습니다
1. 2부터 N까지의 모든 자연수를 나열한다.
2. 나열한 수 중에서 가장 작은수 i를 찾는다.
3. 나열한 수에서 i를 제외한 i의 배수를 모두 제거한다.
4. 더 이상 반복할 수 없을 때까지 2번과 3번과정 반복한다
이를 계속 반복하게 되면 결국 소수밖에 안남을 것입니다.
고민했던것 : 배수들을 찾는 반복문을 어떻게 작성해야할지 막막했다.
--> i를 2부터 하나하나 증가시키고 j=i부터 j=n까지 j에 j를 계속 더하면서 (j=j+i) 배수들을 찾아나갔다.
예를 들어 j=2 라면 2+2, 2+2+2, 2+2+2+2, .... 등등 으로 배수를 구할 수 있다.
<코드구현>
#include <iostream>
#include <vector>
using namespace std;
int main()
{
int n, k;
int count=0;
cin >> n >> k;
vector<int> prime(n + 1);
for (int i=2;i<=n;i++)
{
prime[i]=i;
}
for (int i=2; i<=n;i++)
{
for (int j=i; j<=n;j+=i)
{
if (prime[j]!=0)
{
prime[j] = 0;
count++;
if (count==k)
{
cout << j << '\n';
return 0;
}
}
}
}
return 0;
}학교 실습 과제 에라토스테네스 체 구현
#include<stdio.h>
#include<stdlib.h> //calloc(), free() 함수 선언
#include<math.h> //sqrt()
void eratos(int number, int array[]) { //에라토스테세스의 체 알고리즘 사용하여 소수 구하기
int n, m, to, last, index;
to = (int)sqrt((double)number); // 마지막 나눌 값
for (n = 2; n <= to; n++) { // 바깥쪽 루프
last = number / n; // 마지막 조사 값
for (m = 2; m <= last; m++) { // 안쪽 루프
index = n * m; // 배열의 인덱스
array[index] = 1; // 소수가 아님을 표시한다.
}
} // 이중 반복문이 끝났을 때까지 값이 0인 원소의 인덱스가 소수이다.
}
void print_primes(int value, int* array) { //출력하기
int n;
int count = 0;
printf("%d의 소수 : \n", value);
for (n = 2; n <= value; n++) {
if (array[n] == 0) { // 소수인 것만
printf("%9d", n); // 소수를 9 칸의 공간에 출력한다.
count += 1; // 한 줄에 출력한 소수의 수
if ((count % 8) == 0) // 한 줄에 8 개를 출력하였다면,
printf("\n"); // 다음 줄로 이동한다. }
}
}
printf("\n");
}
int main() {
int number;
int* array; // 문자형 포인터
printf("정수를 입력하세요: "); // 정수 입력
scanf("%d", &number);
if (number > 2) {
array = (int*)calloc(number, sizeof(int)); // 배열 동적 할당
if (array != NULL) {
eratos(number, array); //eratos() 함수 호출
print_primes(number, array); //print_primes()함수 호출
free(array); //동적할당 해제
}
}
return 0;
}#동적할당
- #include <stdlib.h>에 calloc(), malloc() 함수가 들어있다.
- malloc에는 초기화되지 않은 값이 있어서 배열에 쓰레기 값이 저장되어 있다.
- calloc에는 할당 후 해당 메모리공간을 0으로 초기화한다.
- 메모리누수를 막기 위해 동적할당을 해주었으면 해제를 해야함 --> free(void ~~ )
동적할당의 장점?
- 상황에 따라 원하는 크기 만큼의 메모리가 할당되므로 경제적이다.(malloc or calloc)
- 이미 할당된 메모리라도 언제든 크기를 조정할 수 있다(realloc)
동적할당의 단점?
할당 후 free를 통해 해제해주지 않으면 메모리 누수가 나타나고 이는 디버깅에 영향을 미친다.
동적할당의 예시
int *arr=(int *)malloc(10*sizeof(int));
int *arr=(int *)calloc(10,sizeof(int));malloc 은 매개변수로 입력된 크기 만큼을 그대로 할당하는 것이고 calloc은 두번째 매개변수의 크기를 첫번째 매개변수 갯수 만큼을 할당하는 것이다. 위 두 명령어 모두 똑같은 크기의 공간을 확보한다. 단지 calloc은 메모리를 초기화해주지만 malloc에는 쓰레기값이 저장되어있다는 차이가 있다.
