Handle prime numbers in Python / Ruby / PHP / Golang (Go)

Handle prime numbers in Python / Ruby / PHP / Go (Golang)

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.

Find prime numbers below the specified integer

Realized with "Eratosthenes sieve".

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.

Eratosness Sieve Implementation

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.

Etosthenes Sieve with 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))

Eratosthenes Sieve with Ruby 2.4

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

Eratosthenes Sieve with PHP 7.1

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

Eratosthenes Sieve with GoLang

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

Find out if an integer is a prime number

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.

  1. Treat 2, 3, 5 as prime numbers
  2. Even numbers other than 2 are not prime numbers
  3. If it is divisible by 3, 5, it is not a prime number
  4. Increment integers greater than or equal to 7, 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.

Find out if an integer that is Python 3 is a prime number

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

Check if an integer that is Ruby 2.4 is a prime number

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

Check if an integer that is PHP is a prime number

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

Find out if an integer that is Golang is a prime number

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
}

Prime factorization of an integer

I have almost no experience of using it, but since it is related to prime numbers, I will try to realize each.

Prime factorization of integers that are Python3

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]

Prime factorization of integers that are 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]

Prime factorization of integers that are 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]

Prime factorization of integers that are 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]
}

Recommended Posts

Handle prime numbers in Python / Ruby / PHP / Golang (Go)
Grouping combination in Python / Ruby / PHP / Golang (Go)
Overlapping combinations with limits in Python / Ruby / PHP / Golang (Go)
Factorial, permutations, (duplicate) combinations in Python / Ruby / PHP / Golang (Go)
Prime numbers in Python
Handle complex numbers in Python
How to handle JSON in Ruby, Python, JavaScript, PHP
Realize PHP / Python generator with Golang / Ruby
[Scraping Summary] | Python Node.js PHP Ruby Go VBA | Scraping Yahoo! Top in 6 languages
Project Euler # 10 "sum of prime numbers" in Python
GNU GLOBAL (gtags) + α in Go, Ruby, Python
Find prime numbers in Python as short as possible
Handle markdown in python
Handle Parquet in Python
Prime number 2 in Python
python, php, ruby How to convert decimal numbers to n-ary numbers
Handle Ambient data in Python
[Python 3] Prime factorization in 14 lines
Java VS PHP VS Python VS Ruby
Determine prime numbers with python
Handle environment variables in Python
Hello World in various languages [Python / PHP / Java / Perl / Ruby]
Testing with random numbers in Python
Multi-stage selection (Go / C # / Ruby / Python)
Dynamic proxy with python, ruby, PHP
Infinite prime number generator in Python3
Handle posix message queues in python
Handle NetCDF format data in Python
Handle GDS II format in Python
Law of large numbers in python
[Python] nCr mod Compute prime numbers
How to handle Japanese in Python
Avoid nested loops in PHP and Python
Project Euler # 3 "Maximum Prime Factors" in Python
Differences between Ruby and Python in scope
Algorithm learned with Python 4th: Prime numbers
Project Euler # 7 "1000 1st prime number" in Python
[Basic grammar] Differences between Ruby / Python / PHP
Try something like Python for-else in Ruby
Project Euler # 2 "Even Fibonacci Numbers" in Python
How to write Ruby to_s in Python
Differences in string processing between Python, Ruby, JS, PHP (combination and variable expansion)
Solve with Ruby and Python AtCoder ABC084 D Cumulative sum of prime numbers
Prime number enumeration and primality test in Python
Implemented memoization recursion and exploration in Python and Go
Use cryptography module to handle OpenSSL in Python
Y / n processing in bash, python and Go
Project Euler # 13 "Sum of Large Numbers" in Python
Get files, functions, line numbers running in python
POST JSON in Python and receive it in PHP
Prime factorization ver.2 of integers input in Python
Regular expression symbolic group name in Python / Ruby
How to handle datetime type in python sqlite3
Let's see how to count the number of elements in an array in some languages [Go, JavaScript, PHP, Python, Ruby, Swift]