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