A prime number problem that will definitely appear on almost any site when you participate in competitive programming.
Since there are cases where a prime number is obtained for a specified integer or less, whether it is a certain integer or a prime number, and sometimes prime factorization is required, it is necessary to deal with each.
There is a Prime
class in Ruby, but I won't use it here.
Realized with "Eratosthenes sieve".
It is said that the algorithm itself for finding prime numbers exists from ancient Greece. [Wikipedia](https://ja.wikipedia.org/wiki/%E3%82%A8%E3%83%A9%E3%83%88%E3%82%B9%E3%83%86%E3%83 The explanation of% 8D% E3% 82% B9% E3% 81% AE% E7% AF% A9) is very easy to understand. There, we also encounter the inclusion principle (number theorem) at the same time. An example of using the inclusion principle is described in here.
Outputs a prime number for positive integers of 1000 or less. For convenience, either method creates an array with elements up to 1001 so that it can be determined whether it is a prime number or not.
def prime(maximum):
sieve = [True] * maximum
def sieved(prime):
for not_prime in range(prime + prime, len(sieve), prime):
sieve[not_prime] = False
sieve[0] = sieve[1] = False
sieved(2)
for x in range(3, int(maximum ** 0.5) + 1, 2):
if sieve[x]: sieved(x)
return [prime for prime, is_prime in enumerate(sieve) if is_prime]
if __name__ == '__main__':
print(prime(1001))
Created based on Python 3 code.
def prime(maximum)
sieve = Array.new(maximum, true)
sieved = lambda do |prime|
((prime + prime)..sieve.length).step(prime).each do |not_prime|
sieve[not_prime] = false
end
end
sieve[0], sieve[1] = false, false
sieved.call(2)
(3..(maximum ** 2).to_i).step(2).each do |x|
sieved.call(x) if sieve[x]
end
sieve
end
prime(10001).each_with_index do |f, x|
p x if f
end
Created based on Python 3 code.
<?php
function prime(int $maximum) : array {
$sieve = [];
$sieve[0] = $sieve[1] = false;
array_walk(range(2, $maximum - 1), function ($i) use(&$sieve) { $sieve[$i] = true; });
$sieved = function (int $prime) use(&$sieve) : void {
array_walk(range($prime + $prime, count($sieve) - 1, $prime), function($not_prime) use(&$sieve) : void {
$sieve[$not_prime] = false;
});
};
$sieved(2);
array_walk(range(3, intval($maximum ** 0.5), 2), function ($x) use(&$sieve, $sieved) : void {
if ($sieve[$x]) $sieved($x);
});
return array_filter($sieve);
}
array_walk(array_keys(prime(1001)), function ($prime) { print($prime. PHP_EOL); });
Created based on Python 3 code.
package main
import (
"fmt"
"math"
)
func prime(maximum int) [] bool {
sieve := make([]bool, maximum)
for i := range sieve {
sieve[i] = true
}
sieved := func(prime int) {
for i := prime + prime; i < maximum; i += prime {
sieve[i] = false
}
}
sieve[0] = false; sieve[1] = false
sieved(2)
end := int(math.Pow(float64(maximum), 0.5) + 1)
for i := 3; i < end; i += 2 {
if sieve[i] {
sieved(i)
}
}
return sieve
}
func main() {
maximum := 1001
print_prime := func () {
for value, is_prime := range prime(maximum) {
if is_prime {
fmt.Printf("%v\n", value)
}
}
}
print_prime()
}
The above code using the Eratosthenes sieve can also be used, but due to the extra calculations, performance is poor in this case. Therefore, let us consider the algorithm.
2
, 3
, 5
as prime numbers2
are not prime numbers3
, 5
, it is not a prime number7
, and check for a certain integer from 0
by modulo calculation. However, the increment is 4
when it is odd and 2
when it is even.def is_prime(n):
if n < 2:
return False
if n == 2 or n == 3 or n == 5:
return True
if not n & 1:
return False
if n % 2 == 0 or n % 3 == 0 or n % 5 == 0:
return False
f, v, m = True, 7, int(n ** 0.5) + 1
while v < m:
if n % v == 0: return False
v += 4 if f else 2
f = not f
return True
if __name__ == '__main__':
print(is_prime(4993)) # True
def prime?(n)
if n < 2
false
elsif n == 2 || n == 3 || n == 5 then true
elsif n & 1 == 0 then false
elsif n % 2 == 0 || n % 3 == 0 || n % 5 == 0 then false
else
f, v, m = true, 7, (n ** 0.5).to_i + 1
while v < m do
if n % v == 0
false
return
end
v += f ? 4 : 2
f = !f
end
true
end
end
p prime?(4993) # -> true
php7.1
<?php
function is_prime(int $n) : bool {
$r = true;
if ($n < 2) $r = false;
elseif ($n == 2 || $n == 3 || $n == 5) $r = true;
elseif ($n & 1 == 0) $r = false;
elseif ($n % 2 == 0 || $n % 3 == 0 || $n % 5 == 0) $r = false;
else {
$f = true;
$v = 7;
$m = intval($n ** 0.5) + 1;
while ($v < $m) {
if ($n % $v == 0) {
$r = false;
break;
}
$v += $f ? 4 : 2;
$f = !$f;
}
}
return $r;
}
print(is_prime(4993) ? "true" : "false");
package main
import (
"fmt"
"math"
)
func is_prime(n int) bool {
switch {
case n < 2:
return false
case n == 2 || n == 3 || n == 5:
return true
case n & 1 == 0:
return false
case n % 2 == 0 || n % 3 == 0 || n % 5 == 0:
return false
}
f := true
v := 7
m := int(math.Pow(float64(n), 0.5)) + 1
for v < m {
if n % v == 0 {
return false
}
if f {
v += 4
} else {
v += 2
}
f = !f
}
return true
}
func main() {
fmt.Print(is_prime(4993)) // true
}
I have almost no experience of using it, but since it is related to prime numbers, I will try to realize each.
Python has SymPy, but stackoverflow ) Was realized by the method answered in.
def prime_factors(n):
i, factors = 2, []
while i * i <= n:
if n % i:
i += 1
else:
n /= i
factors.append(i)
if n > 1:
factors.append(n)
return factors
if __name__ == '__main__':
print(prime_factors(1200)) # [2, 2, 2, 2, 3, 5, 5]
def prime_factor(n)
i, factors = 2, []
while i * i <= n do
if n % i != 0
i += 1
else
n /= i
factors.push(i)
end
end
if n > 1
factors.push(n)
end
factors
end
p prime_factor(1200) # -> [2, 2, 2, 2, 3, 5, 5]
<?php
function prime_factors(int $n) : array {
$i = 2;
$factors = [];
while ($i * $i <= $n) {
if ($n % $i) $i += 1;
else {
$n /= $i;
$factors[] = $i;
}
}
if ($n > 1) $factors[] = $n;
return $factors;
}
print_r(prime_factors(1200)); // [2, 2, 2, 2, 3, 5, 5]
package main
import "fmt"
func prime_factors(n int) [] int {
factors := make([]int, 0)
i := 2
for i * i <= n {
r := n % i
if r != 0 {
i += 1
} else if r == 0 {
n /= i
factors = append(factors, i)
}
}
if n > 1 {
factors = append(factors, n)
}
return factors
}
func main() {
fmt.Print(prime_factors(1200)) // [2 2 2 2 3 5 5]
}
Recommended Posts