kobanashi3
December 19, 2017 Sieve of Elastenses It is a very useful method for prime factorization. I will introduce it from the principle first. I will not mention the precise meaning of the words as it will be described in plain language. Natural numbers are made up of products of natural numbers. These natural numbers are called the factors of the first natural number. Let N be the initial natural number. Let's average N by product. In other words, let's try √. √ N. Here we get a factor of N greater than √ N. Letting it be a, the square of a is larger than N. Therefore, when dividing the factor of N into two, taking one factor larger than √ N, one becomes a factor smaller than √ N. For this reason, by dividing by the number √ N or less, N can be divided into two factors. If it can not be divided, N is a prime number. Repeat the same operation for the two factors you got in that way. Then repeat the operation until the factor becomes a prime number. By doing so, the number of factoriza...