python coding test course, finding interesting primes

Hello! Today, we will delve deeply into how to solve coding test problems while learning Python. In particular, we will discuss special primes. We will explore what approach we should take to find these special primes.

Problem Description

A special prime is a number that has the property of being a ‘prime’ and satisfies specific patterns or conditions. For example, in addition to common primes like 2, 3, 5, and 7, the special primes we will discuss in-depth must meet the following conditions:

1. All primes except for 2 and 3 can be expressed in the form of 6n ± 1.
2. The sum of the digits must also be a prime number.

Problem: Find special primes within a given range

Please find all special primes up to the given input N. Review the definition of a prime number and find the primes that meet the given conditions.

Input

Natural number N (2 ≤ N ≤ 10,000)

Output

Output each special prime within the given range, one per line.

Example Input

    30
    

Example Output

    2
    3
    5
    7
    11
    13
    17
    19
    23
    29
    

Problem Solving Process

To solve this problem, we must first understand the basic prime number determining algorithm. The traditional method to find primes is the Sieve of Eratosthenes.

1. Prime Determination: Sieve of Eratosthenes

To find the primes, we first need to create a list containing all numbers from 2 to N. Then, we delete the multiples from that list to retain only the primes. This method is time-efficient and simple to implement.

    def sieve_of_eratosthenes(n):
        is_prime = [True] * (n + 1)
        is_prime[0], is_prime[1] = False, False  # 0 and 1 are not primes
        for i in range(2, int(n**0.5) + 1):
            if is_prime[i]:
                for j in range(i * i, n + 1, i):
                    is_prime[j] = False
        return [i for i in range(n + 1) if is_prime[i]]
    

2. Check for Special Prime Conditions

From the list of primes obtained by the above function, we need to check the conditions for special primes. An additional process is required to check if the sum of the digits is also a prime.

    def sum_of_digits(num):
        return sum(int(d) for d in str(num))

    def is_special_prime(prime_list):
        special_primes = []
        for prime in prime_list:
            if prime > 3:  # 2 and 3 can be treated separately as special primes
                digits_sum = sum_of_digits(prime)
                if digits_sum in prime_list:  # Check if the sum of the digits is a prime
                    special_primes.append(prime)

        return special_primes

    def find_special_primes(N):
        primes = sieve_of_eratosthenes(N)
        special_primes = is_special_prime(primes)
        return special_primes
    

Full Implementation Code

Now, let’s combine the above sections to create the complete program code. Through this, we can check if we can correctly find special primes for the given value of N.

    def main(N):
        primes = sieve_of_eratosthenes(N)
        special_primes = is_special_prime(primes)

        for prime in special_primes:
            print(prime)
            
    if __name__ == "__main__":
        N = int(input("Please enter N: "))
        main(N)
    

Conclusion

Today, we solved the problem of finding special primes using Python. Through this process, we reviewed the basic method of determining primes, the Sieve of Eratosthenes, and learned how to check if the sum of the digits is also a prime number.

Such algorithmic problems are very important in real coding tests, so it is necessary to practice and understand them frequently. Explore various problems! Your coding skills will grow to the next level.