[백준 문제풀이] 얼렁뚱땅 1456번 거의 소수 실패~ ><

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

 

a, b = map(int,input().split())

array = [False] * (int(b**0.5)+1)

for i in range(2, (int(b**0.5)+1)) :
	sign = 0
	for j in range(2, (int(i**0.5)+1)) :
		if i%j == 0 :
			sign = 1
			break
	if sign == 0 :
		array[i] = True

cnt = 0
for i in range(len(array)) :
	if array[i] :
		num = i * i
		while True :
			if num > b :
				break
			if (a <= num <= b) :
				cnt += 1
			num = num * i
print(cnt)

# =========================================

a, b = map(int,input().split())


cnt = 0

for i in range(2, (int(b**0.5)+1)) :
	sign = 0
	for j in range(2, (int(i**0.5)+1)) :
		if i%j == 0 :
			sign = 1
			break
	if sign == 0 :
		num = i * i
		while True :
			if num > b :
				break
			if (a <= num <= b) :
				cnt += 1
			num = num * i

print(cnt)

답은 맞는거 같은데 시간초과 뜬당 키키키키 .......................... ㅜ

힝 어케해 어케하냐구