Ein Primzahlproblem, das definitiv auf fast jeder Website auftritt, wenn Sie an wettbewerbsorientierten Programmen teilnehmen. Da es Fälle gibt, in denen eine Primzahl für eine bestimmte Ganzzahl oder weniger erhalten wird, unabhängig davon, ob es sich um eine bestimmte Ganzzahl oder eine Primzahl handelt, und manchmal eine Zerlegung des Primfaktors erforderlich ist, ist es erforderlich, jede zu behandeln. Es gibt eine Prime-Klasse in Ruby, die hier jedoch nicht verwendet wird.
Realisiert mit "Eratostenes Sieb".
Es wird gesagt, dass der Algorithmus selbst zum Finden von Primzahlen aus dem alten Griechenland existiert. [Wikipedia](https://ja.wikipedia.org/wiki/%E3%82%A8%E3%83%A9%E3%83%88%E3%82%B9%E3%83%86%E3%83 Die Erklärung von% 8D% E3% 82% B9% E3% 81% AE% E7% AF% A9) ist sehr leicht zu verstehen. Dort begegnen wir auch dem Ausschlussprinzip (Zahlensatz). Ein Beispiel für die Verwendung des Einschlussprinzips ist hier beschrieben [http://qiita.com/hiroykam/items/3886d6a213cd593fdfab].
Gibt Primzahlen für positive ganze Zahlen von 1000 oder weniger aus. Der Einfachheit halber erstellen beide Methoden ein Array mit Elementen bis zu 1001, sodass festgestellt werden kann, ob es sich um eine Primzahl handelt oder nicht.
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))
Erstellt basierend auf 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
Erstellt basierend auf 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); });
Erstellt basierend auf 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()
}
Es ist möglich, den obigen Code mit dem Eratostenes-Sieb zu verwenden, es gibt jedoch auch zusätzliche Berechnungen, sodass die Leistung in diesem Fall nicht gut ist. Betrachten wir daher den Algorithmus.
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
}
Ich habe fast keine Erfahrung damit, aber da es sich um Primzahlen handelt, werde ich versuchen, jede zu realisieren.
Python hat SymPy, aber stackoverflow ) Wurde durch die in beantwortete Methode realisiert.
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