素数

 1
 2
 3
 4
 5
 6
 7
 8
 9
10

from math import *


def is_prime(n):
	if n < 2:
		return False
	for i in range(2, int(sqrt(n))+1):
		if n % i == 0:
			return False
	return True

1
2
3
4
5
6
7
8
9

def prime(MAX_N):
	lst = [True for _ in range(MAX_N+1)]
	lst[0] = lst[1] = False

	for i in range(2, MAX_N//2):
		if lst[i]:
			for j in range(2*i, MAX_N+1, i):
				lst[j] = False
	return lst

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13

#define MAX 10005
bool prime[MAX];
void init_prime(){
	memset(prime,true,sizeof(prime));
	prime[0]=prime[1]=false;
	for(int i=2;i<=MAX/2;i++){
		if(!prime[i])
			continue;
		for(int j=2*i;j<MAX;j+=i){
			prime[j]=false;
		}
	}
}