Gérer les nombres premiers avec Python / Ruby / PHP / Golang (Go)

Gérer les nombres premiers avec Python / Ruby / PHP / Go (Golang)

Un problème de nombre premier qui apparaîtra certainement sur presque tous les sites lorsque vous participez à une programmation compétitive. Puisqu'il y a des cas où un nombre premier est obtenu pour un entier spécifié ou moins, qu'il s'agisse d'un certain entier ou d'un nombre premier, et qu'il est parfois nécessaire d'effectuer une décomposition en facteurs premiers, il est nécessaire de traiter chacun. Il existe une classe «Prime» dans Ruby, mais elle n'est pas utilisée ici.

Trouver un nombre premier inférieur ou égal à l'entier spécifié

Réalisé avec "tamis Eratostenes".

Tamis Eratostenes

On dit que l'algorithme lui-même pour trouver les nombres premiers existe depuis la Grèce antique. [Wikipédia](https://ja.wikipedia.org/wiki/%E3%82%A8%E3%83%A9%E3%83%88%E3%82%B9%E3%83%86%E3%83 L'explication de% 8D% E3% 82% B9% E3% 81% AE% E7% AF% A9) est très facile à comprendre. Là, on rencontre aussi le principe d'exclusion (théorème des nombres). Un exemple d'utilisation du principe d'inclusion est décrit ici [http://qiita.com/hiroykam/items/3886d6a213cd593fdfab).

Implémentation du tamis Eratosness

Produit des nombres premiers pour les entiers positifs de 1 000 ou moins. Pour plus de commodité, les deux méthodes créent un tableau avec des éléments jusqu'à 1001 afin de pouvoir déterminer s'il s'agit d'un nombre premier ou non.

Tamis Etostenes avec Python 3

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))

• Ceci est le contenu signalé par shiracamus.

Tamis Eratostenes avec Ruby 2.4

Créé à partir du code Python 3.

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

Tamis Eratostenes avec PHP 7.1

Créé à partir du code Python 3.

<?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); });

Tamis Eratostines avec GoLang

Créé à partir du code Python 3.

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()
}

Découvrez si un entier est un nombre premier

Il est possible d'utiliser le code ci-dessus en utilisant le tamis Eratostenes, mais il y a aussi un calcul supplémentaire, donc les performances ne sont pas bonnes dans ce cas. Par conséquent, considérons l'algorithme.

1. Traitez «2», «3», «5» comme des nombres premiers
2. Les nombres pairs autres que «2» ne sont pas des nombres premiers
3. S'il est divisible par «3», «5», ce n'est pas un nombre premier
4. Incrémenter les entiers supérieurs ou égaux à «7», et vérifier si oui ou non à «0» par calcul du surplus pour un certain entier. Cependant, l'incrément est de «4» lorsqu'il est impair et de «2» lorsqu'il est pair.

Découvrez si un entier qui est Python 3 est un nombre premier

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

Vérifiez si un nombre entier qui est Ruby 2.4 est un nombre premier

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

Vérifiez si un entier PHP est un nombre premier

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");

Découvrez si un entier qui est Golang est un nombre premier

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
}

Décomposition en facteurs premiers d'un entier

Je n'ai presque aucune expérience de son utilisation, mais comme il est lié aux nombres premiers, je vais essayer de réaliser chacun.

Décomposition en facteurs premiers des entiers qui sont Python3

Python a SymPy, mais stackoverflow ) A été réalisé par la méthode répondue en.

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]

Décomposition en facteurs premiers des entiers qui sont Ruby 2.4

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]

Décomposition en facteurs premiers des entiers qui sont PHP 7.1

<?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]

Décomposition en facteurs premiers des entiers qui sont Golang

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]
}