백준/1978/소수찾기/Python

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

1620번: 나는야 포켓몬 마스터 이다솜

---

1) C

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#pragma warning(disable:4996)

void sosu(int* arr, int a, int b);
int sosun(int n);

int main(void) {
	int n,num,res; n=num=res = 0;
	scanf("%d", &n);

	for (int i = 0; i <n; i++) { 
		scanf("%d", &num);
		if (num == 1) { continue; }
		if (sosun(num) == 1) { res++; }
	}
	printf("%d", res);
	return 0;
}

void sosu(int * arr, int a, int b) {
	for (int i = 2; i <=b; i++) { 
		if (arr[i] == 0) { continue; }
		for (int j = 2 * (i); j <= b; j += i) { (*(arr + j) = 0); }
	}
}

int sosun(int n) {
	int* arr = (int*)malloc(sizeof(int) * (n + 1));
	for (int i = 2; i <= n; i++) {arr[i] = i;}
	for (int i = 2; i <= n; i++) {
		if (arr[i] == 0) { continue; }
		for (int j = 2 * i; j <= n; j += i) { arr[j] = 0; }
	}
	if (arr[n] == 0) { return 0; }
	else { return 1; }
	free(arr);
}

2) Python

def sosu(n):
    for i in range(2, n):
        if n%i ==0 :
            return 1
    return 0

if __name__ == "__main__":
    N = int(input())
    arr = list(map(int,input().split()))
    result =0

    for i in arr:
        if i==1:
            continue
        if sosu(i) == 0:
            result += 1
    print(result)

---