[백준 1016, 4948, 17390] - Python

취알스 9주차 기타 알고리즘 - 3/5

1016 제곱 ㄴㄴ 수

1-2년 전에 틀렸던 문제를 드디어 풀었다 ㅋ.ㅋ

import sys
input = sys.stdin.readline
MIN, MAX = map(int, input().split())
array = [True] * (MAX-MIN+1) # 주의
count = 0
n = 2
while n * n <= MAX:
    square = n*n
    j = MIN // square
    while square *j <= MAX:
        index = square * j -MIN
        if index >= 0 and array[index]:
            count +=1
            array[index] = False
        j+=1
    n+=1
print(MAX-MIN+1-count)

주의

array = [True for i in range(MAX+1)]

MAX 값이 최대 1,000,000,000,000 + 1,000,000이기 때문에 메모리 초과가 발생할 수 있음.

4948 베르트랑 공준

import sys
import math
input = sys.stdin.readline
primeNo = [True for i in range(246913)]
for i in range(2, 246913):
        if primeNo[i] == True:
            j = 2
            while i * j <= 246912:
                primeNo[i * j] = False
                j += 1
while True:
    n = int(input())
    if n==0:
        break
    ans = 0
    for i in range(n+1, 2*n + 1):
        if primeNo[i]:
            ans += 1
    print(ans)

주의

매 입력마다 소수를 새로 구하면 시간초과 발생

17390 이건 꼭 풀어야 해!

import sys
input = sys.stdin.readline
n, m = map(int, input().split())
array = list(map(int, input().split()))
array.sort()
arrSum = [0]*(n+1)
for i in range(n):
    arrSum[i]=arrSum[i-1]+array[i]
for i in range(m):
    l, r = map(int, input().split())
    print(arrSum[r-1]-arrSum[l-2])