20220221 TIL

에라토스테네스 체

n = int(input())

ch=[0]*(n+1)

cnt=0

for i in range (2,n+1):
if ch[i]==0:
cnt+=1
#start, end, step
for j in range(i,n+1,i):
ch[j]=1

print(cnt)

def reverse(x):
sum=0
while x>0:

    tmp=x%10
    sum=(10*sum)+tmp
    x=x//10
return sum

def isPrime(x):
if x==1:
return False
#소수구하기 16이면 1과 자기자신 빼면 8까지 존재
for i in range(2,x//2+1):
if x%i==0:
return False
else:
return True

n = int(input())
a=list(map(int,input().split()))

for i in a:
so=reverse(i)
if isPrime(so):
print(so,end =' ')