글 읽기 - 그냥 무지성으로 끝까지 돌리고 시간초과

qkgkq18 2년 전 0

소수를 구하는 알고리즘이 뭘까요?

밑에 있는 다른 글 보긴 했는데 파이썬 밖에 몰라서 이해를 못하겠네요

p, k = map(int, input().split())

num_list = []
good = 0
for i in range(2, p):
    if p%i == 0:
        num_list.append(i)
    if len(num_list) == 2:
        break

for i in num_list:
    if i < k:
        print("BAD", i)
        break
    else:
        good += 1

if good == 2:
    print("GOOD")

djm03178 2년 전 1

에라토스테네스의 체에 대해 알아보세요.

사실 이 문제는 소수를 전혀 이용하지 않아도 풀 수 있습니다.

qkgkq18 2년 전 0

ㄴ 코럼 그 다른 방법좀 앙망합니다.

djm03178 2년 전 1

그냥 모든 수로 다 나눠봐도 됩니다.

qkgkq18 2년 전 0

ㄴ 제가 그 방법으로 했는데 시간초과가 나는데요

qkgkq18 2년 전 0

+ 에라토스테네스의 체를 사용해도 체로 거를 숫자들을 모으는데에도 시간초과가 나네요

10^100 이어서

n=1000
a = [False,False] + [True]*(n-1)
primes=[]

for i in range(2,n+1):
  if a[i]:
    primes.append(i)
    for j in range(2*i, n+1, i):
        a[j] = False

djm03178 2년 전 2

p-1까지가 아니라 k-1까지만 나눠보면 됩니다.

qkgkq18 2년 전 0

ㄴ 아 코러네요 어차피 k보다 작은 소수만 보면 되는거니까 감사합니다! 아리카토!

댓글을 작성하려면 로그인해야 합니다.

문제

문제

출처

ICPC

그냥 무지성으로 끝까지 돌리고 시간초과

qkgkq18 2년 전 0

djm03178 2년 전 1

qkgkq18 2년 전 0

djm03178 2년 전 1

qkgkq18 2년 전 0

qkgkq18 2년 전 0

djm03178 2년 전 2

qkgkq18 2년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말