[C언어]백준 1978번: 소수 찾기

https://www.acmicpc.net/problem/1978

1978번: 소수 찾기

---

• 문제

---

• 문제풀이

처음에는 숫자를 입력받아 2부터 자기자신 전 까지 0으로 나누어 떨어지는 값을 제외하고 개수를 세어주면 소수의 개수가 된다.

두번째로는 에라토스테네스의 체를 사용했다.

[알고리즘] 에라토스테네스의 체

---

• 코드 1

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <iostream>
#define _CRT_SECURE_NO_WARNINGS

int main()
{
    int N;
    int arr[1000];
    int count;
    int d = 0;
    scanf("%d", &N);
    for (int i = 0; i < N; i++) {
        count = 0;
        scanf("%d",&arr[i]);
        if (arr[i] == 1) continue;
        for (int j = 2; j < arr[i]; j++) {
            
            if (arr[i] % j == 0) {
                count++;
            }
           
        }
        if (count == 0) {
            d++;
        }
    }
    printf("%d", d);
}

• 코드 2

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

#include <math.h>
#define _CRT_SECURE_NO_WARNINGS

int a[1000001];
int number = 1000001;
void primeNumberSieve() {

	for (int i = 2; i <= number; i++) {
		a[i] = i;
	}

	for (int i = 2; i <= number; i++) {
		if (a[i] == 0) continue; 

		for (int j = 2 * i; j <= number; j += i) {
			a[j] = 0;
		}
	}

	
}
int main(void)
{

	
	int count = 0;
	int N;
		
	scanf("%d", &N);
	int input = 0;
	primeNumberSieve();
	for (int i = 1; i <= N; i++) {
		scanf("%d", &input);
		if (input == 1) continue;
		for (int i = 0; i < number; i++) {
			if (a[i] == input) {
				count++;
			}
		}

	}
	printf("%d", count);

}

---

• 후기

소수를 구하는 법을 알게되었다. 그럼 다수는 버려야하나? 약간 기찻길 문제