アルゴリズムでいこう！- 素数

2020年6月19日 22:23

素数を調べるコードを考えていきます。まずPythonで。

与えられた数字の平方根の値Kkまで割っていき割ることができれば素数ではない”ということf

このサイトで紹介されているコードです。試し割り法です。

def is_prime(n):
   if n == 1:
       return True
   for i in range(2,int(n**0.5) + 1):
       if n % i == 0:
           return False
   return True

is_prime(59)

実行すると

True

と出ます。

次に違うサイトでもみてみます。試し割り法です。

   import math
    
   def trial_division(target):
       dest = int(math.sqrt(target))
    
       for i in range(2,dest):
           if target % i == 0:
               print(str(target) + 'は合成数！')
               return
       print(str(target) + 'は素数！')

trial_division(53)

実行すると

53は素数！

と出ます。

こちらのコードでは"math"をimportして".sqrt"で計算させています。

最初のコードは"n**0.5"で同じ計算をさせています。

Swiftで実装してみます。

func isPrime(_ n:Int)->Bool{
   if n == 1{
       return true
   }
   for i in 2..<(Int(sqrt(Double(n)))+1){
       if n % i == 0{
        return false
       }
   }
   
   return true
}

isPrime(53)

と実行すると"true"となります。

この記事が気に入ったらサポートをしてみませんか？