Coding-Test Day 1

 

https://spartacodingclub.framer.website/challenge?utm_source=community&utm_medium=earned&utm_campaign=%EC%8A%A4%EC%BD%94%ED%81%B4%EC%9C%A0%EB%A3%8C&utm_content=%EB%A6%AC%EB%93%9C%ED%9A%8D%EB%93%9D&utm_term=%EC%9E%91%EC%8B%AC%ED%81%B0%EC%9D%BC_%EC%B9%B4%ED%8E%98%EC%BB%A4%EB%AE%A4%EB%8B%88%ED%8B%B0_250707

 

By chance, I saw an advertisement for a one-question coding-test challenge per day, so i applied and did a challenge to solve three questions once a day on weekdays and on weekends.

 

It's a two-week challenge, and I'd like to explain one by one what I've solved so far.

And I will also write down the shortcomings after looking at the commentary of senior developers.

 

Here, "Baekjoon" and "Programmers" were brought from an organization that took a coding test similar to "LeetCode" and conducted the challenge.

 

 

First of all, a problem of outputting all prime numbers greater than or equal to M and less than or equal to N has emerged.

 

I simply checked from 2 to x-1 and judged that it was a prime number if not divided and separated.

 

def is_prime_number(x):
	for i in range(2, x):
    	if x % i == 0:
        	return False
        else:
        	return True
a = int(input())
target = int(input())

for i in range(a, target + 1):
	if is_prime_number(i):
    	print(i)

However, I learned that it is inefficient to divide from 2 to x-1, and that it is efficient to divide the square root.

 

Because if any number x can be expressed as a product of two numbers, One of them is because it must be below √x.

 

So it's enough to check up to √n.

 

Another important point is the for-else grammar. It's an unusual grammer that's only available in Python,

It's a structure in which an else block is executed when a repetition sentence is finished without a break.

 

If you use this, you can determine the number of people.

 

This is an implementation problem that combines decimal discrimination + use of repeated statements + understanding of Python grammar.

 

But, if there's a lot of input and it's big, you should consider a sieve of Eratosthenes.

 

n, m = map(int, input().split())

for i in range(n, m+1):
	if i == 1:
    	continue
    for j in range(2, int(i ** 0.5) + 1):
    	if i % j == 0:
        	break
    else:
    	print(i)

 

Optimization Tip

1. Let's divide only the square root. -> It's too slow to divide everything from 2 to i-1 -> If you look at the √i, the speed decreases significantly.

2. Clean the conditions with the for-else

-> If there is no break in the repetition sentence, an else is executed, so you can naturally judge whether there is a prime number.

 

3. Make sure to deal with 1 separately -> I often make mistakes, but 1 is not a prime number, so let's skip to continue.

 

 

Associated Problem

• In the acutal coding-test, let's consider simple conditional branching and optimization.
• When determining prime numbers, you only need to look up to √ n.