hyjin1117   1년 전

Hi

I was doin silver random defense with tier number hidden

well, this problem looks pretty difficult to be silver

my approach was erathosthenes with binary search query

I thought this problem would be not less than silver1

but actually this is S4 !

I searched faster code

and it was just naive

You should understand the emptiness I feel

yoonjin67   1년 전

yup, it could be naive when you implement 'way-too-fast' codes. This still can be achieved with a simple technique by 'storing found prime numbers'.

You can divide current number with stored primes, and determine whether it is, or not.

initially prime number 2 is the smallest(and unique because it's only even number among prime numbers), so push 2 in found prime number's list(now I will call this f_plist).

when the order of three,

3 / 2 != 0

push 3

when the order of four,

4 / 2 == 0

skip

when the order of five,

5 / 2 == 1

5 / 3 == 2

push 5

when the number of six,

6 / 2 == 0

skip

when the number of seven,

7 / 2 == 1

7 / 3 == 1

7 / 5 == 2

push 7

...


with this method, you can save some of computing powers(because it would not calculate {target / nonprime} result).

I hope it helps,

thank you.


Lee Yunjin, Daegu Univ Computer SW 21.


댓글을 작성하려면 로그인해야 합니다.