Go to Qiita Advent Calendar 2024 Top
LoginSignup
7
6

Delete article

Deleted articles cannot be recovered.

Draft of this article would be also deleted.

Are you sure you want to delete this article?

More than 5 years have passed since last update.

@TD12734

様々なプログラミング言語における素数判定

Posted at

#複数の言語で素数判定プログラムを書いた経緯
個人的に色んな言語を学習したくなったのだが、Hello Worldだけでは物足りないので素数判定プログラムを書く事にした。素数判定プログラムを書ければ各言語の基本仕様を理解したつもりになれると考えている。具体的には以下を理解出来るだろう。

  • 変数の宣言、初期化、代入
  • コマンドラインへの入出力
  • 条件分岐
  • ループ文
  • 引数と返り値がある関数の定義
  • 数値と文字列の相互変換
  • 真偽値の文字列への変換
  • 文字列結合
  • 文字列置換(フォーマット)
  • 平方根の計算
  • コメント文の追加

当初はフィボナッチ数列で行おうと思ったが先人が存在したので素数を判定する事にした。二番煎じかもしれないけど素数判定も大きな需要があるでしょ。

#素数判定の流れ
素数とは1と自分自身以外に正の約数を持たない自然数で、1でない数のことである。例えば2,3,5など。素数では無い自然数は合成数と呼ばれる。今回は与えられた整数に対して以下の流れで処理を行って素数かどうかを判定する。

  1. 与えた整数が2であれば素数である。
  2. 与えた整数を2で割り切れる(つまり偶数)、または与えた整数が2未満なら素数では無い。
  3. 与えた整数を3以上の奇数で割る。割り切れれば素数では無い。割り切れなければ1個大きい奇数(つまり+2した値)で割り切れるか判定する。与えた整数の平方根以下の最大の奇数の全ての奇数で割り切れなかった場合、与えた整数は素数である。

詰まる所、試し割り法で素数判定を行う。
流れ3について、与えた数未満の全ての数で割る必要は無い。まず、流れ2をパスした時点で与えた整数は奇数なので偶数で割る必要は無い。また、合成数は

自身の平方根以下で2以上の自然数×自身の平方根以上の自然数

と表現可能である。(例：105=3×35、49=7×7)
2から自身の平方根以下の最大の自然数のどれでも割り切れない数は合成数ではない、つまり素数である。なので平方根以下の最大の奇数まで調べるだけで良い。

#サンプルプログラム
##動作環境
今回はpaiza.ioでプログラムを動かす。ローカルでやる場合、一部の言語は開発環境の構築やコンパイルがすっっっっっごく面倒なので煩わしい作業が一切不要なpaiza.ioを使用する。
ローカルの環境で動作させたい場合はコードの一部の変更すれば多分動くだろう。

##動作サンプル
以下のgifみたいな手順で入力した数値が素数かどうかを判定可能である。
prime.gif

##プログラムの構成
原則として、プログラムは以下の2つの関数で構成されている。ただし、Main関数が不要な場合は省略する。

  1. 入力された数値を取得し、その数値が素数かどうかを表示する「Main」関数
  2. 引数として数値を受け取り、返り値として引数が素数ならtrue、そうでなければfalseを返す「IsPrime」関数

IsPrime関数では上述の手順に沿って素数判定を行う。

##プログラムの処理の流れ
原則として、以下の流れに沿ってプログラムを動作させる。

  1. コマンドラインに入力された整数値を変数nに代入する。整数値以外は入力されない前提。
  2. "{nの値} is a prime number : {IsPrime(n)の返り値}"をコマンドラインに出力する。この文は文末で改行する。

例えば「5」と入力すれば「5 is a prime number : true」、「6」と入力すれば「6 is a prime number : false」のように表示される。

##プログラミング言語の順序
基本的にTIOBEのランキングの順番(2019年6月参照)に従う。

##Java

Java
import java.util.*;

public class Main
{
    public static void main(String[] args)
    {
        int n = new Scanner(System.in).nextInt();//入力された数値をnに代入
        System.out.println(String.valueOf(n) + " is a prime number : " + String.valueOf(IsPrime (n)));//結果を出力
    }
    
    private static boolean IsPrime(int n)//trueなら素数
    {
        if (n == 2)
        {
            return true;
        }
        else if (n % 2 == 0 || n < 2)
        {
            return false;
        }
        else
        {
            for (int i = 3; i <= Math.sqrt(n); i += 2)
            {
                if (n % i == 0)
                {
                    return false;
                }
            }
        }
        return true;
    }
}

##C言語
C言語でbool使うイメージは無いし、使った所で文字変換出来ないから素数かどうかは0,1で返す事にした。

C言語
#include <stdio.h>
#include <math.h>

int IsPrime(int n)//0なら素数
{
    if (n == 2)
    {
        return 0;
    }
    else if (n % 2 == 0 || n < 2)
    {
        return 1;
    }
    else
    {
        for (int i = 3; i <= sqrt(n); i += 2)
        {
            if (n % i == 0)
            {
                return 1;
            }
        }
    }
    return 0;
}

int main(void)
{
    int n;
    scanf("%d", &n);//入力された数値をnに代入
    printf("%d is a prime number : %s\n", n, IsPrime(n) == 0 ? "true" : "false");//結果を出力
    return 0;
}

##Python
Python2とPython3の両方で動作する。

Python
# coding: utf-8
def IsPrime(n):#trueなら素数
    if n == 2:
        return True
    elif n % 2 == 0 or n < 2:
        return False
    else:
        for i in range(3, int(round(n**0.5)) + 1, 2):
            if n % i == 0:
                return False
    return True

n = int(input())#入力された数値をnに代入
print ("%d is a prime number : %s" % (n, IsPrime(n)))#結果を出力

##C++
boolの文字変換が少し面倒。

C++
#include <iostream>
#include <cmath>
//using namespace std;//入出力でstd::を付けたくなければコメントを外す

bool IsPrime(int n);

int main()
{
    int n;
    std::cin >> n;//入力された数値をnに代入
    std::cout << n << " is a prime number : " << std::boolalpha << IsPrime(n) << std::endl;//結果を出力、std::boolalphaを付けないとboolが0,1になる
    return 0;
}

bool IsPrime(int n)//trueなら素数
{
    if (n == 2)
    {
        return true;
    }
    else if (n % 2 == 0 || n < 2)
    {
        return false;
    }
    else
    {
        for (int i = 3; i <= sqrt(n); i += 2)
        {
            if (n % i == 0)
            {
                return false;
            }
        }
    }
    return true;
}

##Visual Basic .NET

VB
Public Class Compiler
  Shared Sub Main
    Dim n As Integer = Console.ReadLine()'入力された数値をnに代入'
    Console.WriteLine (n.ToString() + " is a prime number : " + IsPrime (n).ToString())'結果を出力'
  End Sub
  
  Shared Function IsPrime(n as integer) As Boolean'Trueなら素数'
    If n = 2 Then
      Return True
    Else If n Mod 2 = 0 Or n < 2 Then
      Return False
    Else
      For i As Integer = 3 To Math.Sqrt(n) Step 2
        If n Mod i = 0 Then
          Return False
        End If
      Next
      Return True
    End If
  End Function
End Class

##C#

C#
//using System;//入出力、平方根の計算でSystem.を付けたくなければコメントを外す

public class Class
{
    public static void Main()
    {
        int n = int.Parse(System.Console.ReadLine());//入力された数値をnに代入
        System.Console.WriteLine(n.ToString() + " is a prime number : " + IsPrime (n).ToString());//結果を出力
    }
    
    private static bool IsPrime(int n)//trueなら素数
    {
        if (n == 2)
        {
            return true;
        }
        else if (n % 2 == 0 || n < 2)
        {
            return false;
        }
        else
        {
            for (int i = 3; i <= System.Math.Sqrt(n); i += 2)
            {
                if (n % i == 0)
                {
                    return false;
                }
            }
        }
        return true;
    }
}

##JavaScript

JavaScript
process.stdin.resume();
process.stdin.setEncoding('utf8');
process.stdin.on('data', function (chunk)
{
    var n = Number(chunk);//入力された数値をnに代入
    console.log(String(n) + " is a prime number : " + String(IsPrime (n)));//結果を出力
});

function IsPrime(n)//trueなら素数、「var IsPrime = function(n)」とも書ける
{
    if (n === 2)
    {
        return true;
    }
    else if (n % 2 === 0 || n < 2)
    {
        return false;
    }
    else
    {
        for (var i = 3; i <= Math.sqrt(n); i += 2)
        {
            if (n % i === 0)
            {
                return false;
            }
        }
    }
    return true;
}

##PHP
boolの文字変換が少し面倒。

PHP
<?php
$n = intval(fgets(STDIN));//入力された数値をnに代入
echo "$n is a prime number : " . var_export(IsPrime($n), true) . "\n";//結果を出力

function IsPrime($n)//trueなら素数
{
    if ($n == 2)
    {
        return true;
    }
    else if ($n % 2 == 0 || $n < 2)
    {
        return false;
    }
    else
    {
        for ($i = 3; $i <= sqrt($n); $i += 2)
        {
            if ($n % $i == 0)
            {
                return false;
            }
        }
    }
    return true;
}
?>

##Swift

Swift
import Foundation

func IsPrime(n: Int) -> Bool//trueなら素数
{
    if (n == 2)
    {
        return true
    }
    else if (n % 2 == 0 || n < 2)
    {
        return false
    }
    else
    {
        for i in stride(from: 3, to: Int(ceil(sqrt(Double(n)))) + 1, by: 2)
        {
            if (n % i == 0)
            {
                return false
            }
        }
    }
    return true
}

let n : Int = Int(readLine()!)! //入力された数値をnに代入
print("\(n) is a prime number : \(IsPrime(n: n))")//結果を出力

##Objective-C

Objective-C
#import <Foundation/Foundation.h>

bool IsPrime(int n);

int main()
{
    @autoreleasepool
    {
        int n;
        scanf("%d", &n);//入力された数値をnに代入
        printf("%d is a prime number : %s\n", n, IsPrime(n) ? "true" : "false");//結果を出力
        return 0;
    }
}

bool IsPrime(int n)//trueなら素数
{
    if (n == 2)
    {
        return true;
    }
    else if (n % 2 == 0 || n < 2)
    {
        return false;
    }
    else
    {
        for (int i = 3; i <= sqrt(n); i += 2)
        {
            if (n % i == 0)
            {
                return false;
            }
        }
    }
    return true;
}

##Ruby

Ruby
def IsPrime(n)#trueなら素数
    if n == 2 then
        return true
    elsif n % 2 == 0 || n < 2 then
        return false
    else
        i = 3
        while i <= Math.sqrt(n)
            if n % i == 0 then
                return false
            end
            i += 2
        end
        return true
    end
end

n = readline.to_i#入力された数値をnに代入
puts "#{n} is a prime number : #{IsPrime(n)}"#結果を出力

RubyにはPrimeクラスが用意されており、これを用いる事でも素数判定が可能。

Ruby_Prime
require 'prime'
n = readline.to_i#入力された数値をnに代入
puts "#{n} is a prime number : #{Prime.prime?(n)}"#結果を出力

##Go

Go
package main
import (
    "fmt"
    "os"
    "bufio"
    "strconv"
    "math"
)
func main() {
    scanner := bufio.NewScanner(os.Stdin)
    scanner.Scan()
    n, _ := strconv.Atoi(scanner.Text())//入力された数値をnに代入
    fmt.Println(n, "is a prime number :", IsPrime(n))//結果を出力
}

func IsPrime(n int) bool {//trueなら素数
    if n == 2 {
        return true
    } else if n % 2 == 0 || n < 2 {
        return false
    } else {
        for i := 3; float64(i) <= math.Sqrt(float64(n)); i += 2 {
            if n % i == 0 {
                return false
            }
        }
    }
    return true
}

##Perl

Perl
$n = <STDIN>;#入力された数値をnに代入
print "${n} is a prime number : @{[&IsPrime($n)]}\n";#結果を出力

sub IsPrime #trueなら素数
{
    my ($n) = @_;#引数を受け取る、myを付けて局所化しないと1が代入される
    if ($n == 2)
    {
        return true;
    }
    elsif ($n % 2 == 0 || $n < 2)
    {
        return false;
    }
    else
    {
        for ($i = 3; $i <= sqrt($n); $i += 2)
        {
            if ($n % $i == 0)
            {
                return false;
            }
        }
    }
    return true;
}

##R言語
数値入力の時、最後に改行を入れないと警告が出されるがプログラムは問題なく動作する。

R言語
IsPrime <- function(n)#trueなら素数
{
    if (n == 2)
    {
        return (TRUE)
    }
    else if (n %% 2 == 0 || n < 2)
    {
        return (FALSE)
    }
    else
    {
        for (i in 2:sqrt(n))
        {
            if (n %% i == 0)
            {
                return (FALSE)
            }
        }
    }
    return (TRUE)
}

n <- as.integer(readLines("stdin")[1])#入力された数値をnに代入
cat(n, "is a prime number :", IsPrime(n), "\n")#結果を出力

##D言語

D言語
import std.stdio, std.conv, std.array, std.math;
void main()
{
    int n = readln.split[0].to!int;//入力された数値をnに代入
    writefln("%s is a prime number : %s", n, IsPrime(n));//結果を出力
}

bool IsPrime(int n)//trueなら素数
{
    if (n == 2)
    {
        return true;
    }
    else if (n % 2 == 0 || n < 2)
    {
        return false;
    }
    else
    {
        for (int i = 3; i <= sqrt(float(n)); i += 2)
        {
            if (n % i == 0)
            {
                return false;
            }
        }
    }
    return true;
}

##COBOL
数値入力の時、最後に改行を入れる必要がある。

COBOL
IDENTIFICATION DIVISION.
program-id. IsPrime.
AUTHOR. TD12734.

ENVIRONMENT DIVISION.
DATA DIVISION.

WORKING-STORAGE SECTION.
01 n PIC S9(9) COMP-5.
01 result PIC 9(1) VALUE 0.
01 i PIC S9(9) COMP-5 VALUE 3.
01 resultstr PIC X(8).

PROCEDURE DIVISION.
Main.
accept n.*>入力された数値をnに代入
PERFORM IsPrime.*>手続き「IsPrime」を呼ぶ
IF result = 0 *>resultの値に応じてtrue/falseの文字列を設定
    SET resultstr TO "true"
ELSE
    SET resultstr TO "false"
END-IF.
display n " is a prime number : " resultstr.*>結果を出力
STOP RUN.

IsPrime.*>resultが0なら素数
IF n = 2 OR n = 3
    SET result TO 0
ELSE IF FUNCTION REM (n 2) = 0 OR n < 2 *>COBOLにelse-ifは無いのでelse文の中にif文を書き、elseとifを同じ行に書くややこしい手法を取っている
    SET result TO 1
ELSE
    PERFORM FUNCTION SQRT (n) TIMES
        IF FUNCTION REM (n i) = 0
        SET result TO 1
        EXIT PERFORM
        END-IF
        ADD 2 TO i
    END-PERFORM
END-IF *>IF FUNCTION~のIFを閉じる
END-IF.*>IF n = 2~のIFを閉じる
STOP RUN.

#あとがき
Javaみたいなコンパイラ言語はコンパイラ言語で、Pythonみたいなインタプリタ言語はインタプリタ言語で似たような形式で書けるのだと身を以て理解した。
また、今回書いた言語の中でもObjective-CとCOBOLは全然慣れていないので、機会があればこれらの言語について理解を深めていきたい。使う機会は無さそうだけど

7
6
4

Register as a new user and use Qiita more conveniently

  1. You get articles that match your needs
  2. You can efficiently read back useful information
  3. You can use dark theme
What you can do with signing up
Sign upLogin
7
6

Delete article

Deleted articles cannot be recovered.

Draft of this article would be also deleted.

Are you sure you want to delete this article?