[백준] 1644번: 소수의 연속합 (feat indexError)

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

initial

I immediately knew that we had to use sieve of eratosthenes.

def sieve_of_eratosthenes(n):
    is_prime = [True] * (n + 1)
    is_prime[0] = is_prime[1] = False  # 0 and 1 are not prime

    for p in range(2, int(n**0.5) + 1):
        if is_prime[p]:
            for multiple in range(p * p, n + 1, p):
                is_prime[multiple] = False

    primes = [i for i, prime in enumerate(is_prime) if prime]
    return primes

One issue I struggled with was indexError. Notice if n of value 1 is passed, then this sieve def logic where we iterate p from 2 will cause IndexError. So we have to handle this value 1 edge case before we invoke this method to prevent that error.

like this:

n = int(input())
if n==1:
    print(0)
    exit()

Also, 2 pointer should not be prematurely ended. I mistakenly placed if right==len(primes)-1 but that is valid as it is at the last value of our primes list. Instead, we should break out of the llop when it is at len(primes), which is outside the loop.

solution

n = int(input())
if n==1:
    print(0)
    exit()
    
def sieve(n):
    is_prime = [True for _ in range(n+1)]
    is_prime[0]=is_prime[1]=False
    for p in range(2, int(n**0.5)+1):
        if is_prime[p]:
            for multiple in range(p*p, n+1,p):
                is_prime[multiple]=False
    primes = [i for i,prime in enumerate(is_prime) if prime]
    return primes
primes = sieve(n)
left=0
right=0
sum=primes[0]
ans=0

while left<=right and right<len(primes):
    if sum==n:
        ans+=1
        sum-=primes[left]
        left+=1
    elif sum<n:
        right+=1
        if right==len(primes):
            break
        sum+=primes[right]
    else:
        sum-=primes[left]
        left+=1
print(ans)

for more optimised solution in 2 pointer

while left<=right and right<len(primes):
    if sum<=n:
        if sum==n:
            ans+=1
        right+=1
        if right==len(primes):
            break
        sum+=primes[right]
    else:
        sum-=primes[left]
        left+=1
print(ans)

complexity:

The complexity of your algorithm is mainly determined by the Sieve of Eratosthenes and the subsequent processing.

1. Sieve of Eratosthenes: Generating prime numbers up to n using the Sieve of Eratosthenes has a time complexity of approximately O(n log log n) and a space complexity of O(n).

2. Loop: Your loop iterates over the list of prime numbers once, so it has a time complexity of O(len(primes)). In the worst case, when n is large and you have many prime numbers up to n, the loop can be roughly O(n/log log n).

Overall, the time complexity is dominated by the Sieve of Eratosthenes, making it approximately O(n log log n). The space complexity is O(n) due to the storage of prime numbers.

This algorithm efficiently finds the number of ways to represent n as a sum of consecutive prime numbers.

log log n time

In computational complexity analysis, "log log n" represents the logarithm of the logarithm of a number. It is a concept used to describe the growth rate of certain algorithms.

Let me clarify:

• "log n" stands for the logarithm base 2 of a number n. It describes how many times you need to divide n by 2 to reach 1.

• "log log n" is the logarithm base 2 of "log n." It means taking the logarithm of "log n."

The "log log n" term appears in certain algorithms, like the Sieve of Eratosthenes used in your previous code, to describe their growth rate more precisely. It indicates that the algorithm's time complexity grows very slowly, making it quite efficient for large values of n.

For example, if you have n = 1,000, "log n" is 10 because 2^10 = 1,024, and "log log n" is approximately 3 because log(10) ≈ 3. So, in this case, you have "log log n" ≈ 3.

In summary, "log log n" represents a double logarithm, which is a very slow-growing function and helps characterize the efficiency of algorithms that have a runtime of O(n log log n).