« ^ »

試し割り法で素数を判定する

所要時間: 約 1分

試し割り法

from unittest import TestCase


def is_prime_trial_division(num):
    power = num ** 2
    if num >= 2:
        for ii in range(2, num):
            if ii ** 2 > power:
                break
            elif num % ii == 0:
                break
        else:
            return True
    return False


PRIMES = [
    2,
    3,
    5,
    7,
    11,
    13,
    17,
    19,
    23,
    29,
    31,
    37,
    41,
    43,
    47,
    53,
    59,
    61,
    67,
    71,
    73,
    79,
    83,
    89,
    97,
]


class TrialDivisionTest(TestCase):
    def test_it(self):
        for ii in range(100):
            self.assertEqual(ii in PRIMES, is_prime_trial_division(ii), ii)