[백준] 6219번: 소수의 자격

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

initial

A typical sieve of erasthostenes but I tried solving via just iterating from left to right number and checking if it is prime but it ran to runtime. SO plan well before you implement it.

Solution

initial runtime over solution

import math

def checkPrime(num):
    if num <= 1:
        return False
    if num <= 3:
        return True
    for j in range(2, int(math.sqrt(num)) + 1):
        if num % j == 0:
            return False
    return True

left, right, num = map(int, input().split())
count = 0

for i in range(left, right + 1):
    if checkPrime(i):
        num_str = str(i)
        if str(num) in num_str:
            count+=1

print(count)

sieve sol

import math

left, right, digit = map(int, input().split())

def sieve(start, num):
    is_prime = [True for _ in range(num + 1)]
    is_prime[0] = is_prime[1] = False

    for i in range(2, int(math.sqrt(num)) + 1):
        if is_prime[i]:
            for multiple in range(i * i, num + 1, i):
                is_prime[multiple] = False

    count = 0

    for i in range(start, num + 1):
        if is_prime[i] and str(digit) in str(i):
            count += 1

    return count

ans = sieve(left, right)
print(ans)

complexity

sieve is n log log n

The time complexity of the provided code is primarily determined by the Sieve of Eratosthenes algorithm, which finds prime numbers in a given range. The Sieve of Eratosthenes has a time complexity of O(n log log n), where 'n' is the upper limit of the range (in this case, 'right').

The space complexity is determined by the array is_prime, which stores a boolean value for each number in the range. The space complexity is O(n) because it stores information for each number in the range.

So, the time complexity is O(n log log n), and the space complexity is O(n).