Как найти простые числа программирование

Алгоритм нахождения простых чисел

Оптимизация алгоритма нахождения простых чисел

2 3 5 7 11 13 17 19 23 29 31… $250.000…

Дело было давно, в университете, когда мы начали изучать язык программирования Pascal и домашним заданием стало создание алгоритма нахождения простых чисел.

Алгоритм был придуман и тутже реализован на изучаемом языке. Программа запрашивала у пользователя число N и искала все простые числа до N включительно. После первого успешного теста сразу же возникло непреодолимое желание ввести N = «много». Программа работала, но не так быстро как хотелось бы. Естественно, дело было в многочисленных проверках (порядка N*N/2), поэтому пришлось избавиться от лишних. В итоге получилось 5 похожих алгоритмов каждый из которых работал быстре предыдущего. Недавно захотелось их вспомнить и реализовать, но на этот раз на Python.

Итак, поехали. Первый алгоритм, ударивший в студенческую голову, продемонстрирован в Листинге 1.

# Листинг 1
# вводим N
n = input("n=")
# создаем пустой список для хранения простых чисел
lst = []
# в k будем хранить количество делителей
k = 0
# пробегаем все числа от 2 до N
for i in xrange(2, n+1):
    # пробегаем все числа от 2 до текущего
    for j in xrange(2, i):
        # ищем количество делителей
        if i % j == 0:
            k = k + 1
    # если делителей нет, добавляем число в список
    if k == 0:
        lst.append(i)
    else:
        k = 0
# выводим на экран список
print lst

Очень быстро понимаешь, что в подсчете делителей каждого числа нет никакой надобности и поэтому переменную k можно освободить от своих обязанностей. Действительно, если хотябы один делитель имеется, то число уже не простое. Смотрим Листинг 2.

# Листинг 2
n = input("n=")
lst = []
for i in xrange(2, n+1):
    for j in xrange(2, i):
        if i % j == 0:
            # если делитель найден, число не простое.
            break
    else:
        lst.append(i)
print lst

Конструкция break позволяет нам завершить выполнение внутреннего цикла и перейти к следующей итерации внешнего.
Далее возникает вопрос: «а зачем делить на 4, если на 2 число не делится?». Приходим к выводу, что искать делители нужно только среди простых чисел не превышающих делимое. Наш алгоритм превращается в… см. Листинг 3.

# Листинг 3
n = input("n=")
lst=[]
for i in xrange(2, n+1):
    # пробегаем по списку (lst) простых чисел
    for j in lst:
        if i % j == 0:
            break
    else:
        lst.append(i)
print lst

А потом вспоминаем теорию чисел и понимаем, что переберать надо только числа, не превосходящие корня из искомого. К примеру, если число M имеет делитель pi, то имеется делитель qi, такой, что pi * qi = M. То есть, чтобы найти пару, достаточно найти меньшее. Среди всех пар, предполагаемая пара с максимальным наименьшим — это пара с равными pi и qi, то есть pi * pi = M => pi = sqrt(M). Смотрим Листинг 4.

# Листинг 4 
from math import sqrt
n = input("n=")
lst=[]
for i in xrange(2, n+1):
    for j in lst:
        if j > int((sqrt(i)) + 1):
            lst.append(i)
            break
        if (i % j == 0):
            break
    else:
        lst.append(i)
print lst

Код из Листинга 4 при N=10000 выполняется примерно в 1000 раз быстрее, чем самый первый вариант. Есть еще один «ускоритель», проверять только те числа, которые заканчиваются на 1, 3, 7 или 9 (так как остальные очевидно делятся на 2 или 5). Наблюдаем Листинг 5.

# Листинг 5
from math import sqrt
n = input("n=")
lst=[]
for i in xrange(2, n+1):
    if (i > 10):
        if (i%2==0) or (i%10==5):
            continue
    for j in lst:
        if j > int((sqrt(i)) + 1):
            lst.append(i)
            break
        if (i % j == 0):
            break
    else:
        lst.append(i)
print lst

В следствии незначительного изменения Листинга 5 получаем небольшую прибавку в скорости:

# Листинг 6
from math import sqrt
n = input("n=")
lst=[2]
for i in xrange(3, n+1, 2):
    if (i > 10) and (i%10==5):
        continue
    for j in lst:
        if j > int((sqrt(i)) + 1):
            lst.append(i)
            break
        if (i % j == 0):
            break
    else:
        lst.append(i)
print lst

Итого: Программа из последнего листинга выполняется, примерно, в 1300 раз быстрее первоначального варианта.
Я не ставил перед собой задачи написать программу максимально быстро решающую данную задачу, это скорее демонстрация начинающим программистам того, что правильно составленный алгоритм играет далеко не последнюю роль в оптимизации Ваших программ.

P.S.
Благодаря замечаниям получаем Листинг 7:

# Листинг 7
n = input("n=")
lst=[2]
for i in xrange(3, n+1, 2):
	if (i > 10) and (i%10==5):
		continue
	for j in lst:
		if j*j-1 > i:
			lst.append(i)
			break
		if (i % j == 0):
			break
	else:
		lst.append(i)
print lst

при N=10000, поучаем время:
time 1 = 26.24
time 2 = 3.113
time 3 = 0.413
time 4 = 0.096
time 5 = 0.087
time 6 = 0.083
time 7 = 0.053

Решето Эратосфена:

# Листинг 8
n = input("n=")
a = range(n+1)
a[1] = 0
lst = []

i = 2
while i <= n:
    if a[i] != 0:
        lst.append(a[i])
        for j in xrange(i, n+1, i):
            a[j] = 0
    i += 1
print lst

Результаты при n = 1 000 000:
time 7 = 7.088
time 8 = 1.143

Given two numbers L and R, the task is to find the prime numbers between L and R.

Examples:

Input: L = 1, R = 10
Output: 2 3 5 7
Explanation:
Prime number between the 1 and 10 are 2, 3, 5, and 7 

Input: L = 30, R = 40
Output: 31 37 

Approach 1:

The idea is to iterate from in the range [L, R] and check if any number in the given range is prime or not. If yes then print that number and check for the next number till we iterate all the numbers.

Below is the implementation of the above approach:

Time Complexity: O((R-L)*N), where N is the number, and L and R are the given range.
Auxiliary Space: O(1)

Approach 2: (Optimized Approach)

An optimized approach of the above is to check until square root of each value instead of half. We also don’t check even numbers.

Approach:

The approach behind this solution is:

1. We first print 2 if 2 is in range as 2 is the only even prime number.
2. Then we iterate all the odd numbers only.
3. In every iteration we check and print if the number is prime or not using isPrime function.
4. In isPrime function:
   • We will first deal with a few numbers such as 1, 2, 3 in a case.
   • Then we deal with the numbers which are divisible by 2 and 3 in a separate case.
   • For remaining numbers:
     • Iterate from 5 to sqrt(n) and check for each iteration whether (that value) or (that value + 2) divides n or not.
       • If we find any number that divides, then we return false.
     • Again increment the value by 6 [because any prime can be expressed as 6n+1 or 6n-1]. 
   • If any number can’t divide the number, then we return true.

Below is the implementation of the above approach:

Time Complexity: O((R-L)*sqrt(N)), where N is the number, and L and R are the given range.
Auxiliary Space: O(1)

Approach 3:

An alternative approach to implement the same code would be to use a sieve algorithm. A sieve algorithm starts by creating a list of all the numbers in the desired range and then crossing out the multiples of each prime number. The resulting list will contain only the prime numbers.

The prime numbers in this range are: 5 7 11 13 17 19 23 29 31 37 41 43 47 53 59 61 67 71 73 79 83 89 97 

Time Complexity : O(n log(log(n))
Auxiliary Space: (R-l), where R and l are the starting and ending ranges. 

Last Updated :
17 May, 2023

Like Article

Save Article

чтобы проверить что число простое в данном алгоритме он делится на все числа от 2 до int(number / 2) включительно (поэтому и half + 1)

очевидно, что если число не делится на какое-то число в диапазоне 0 ..number / 2, то оно не делится на любое числа в диапазоне number / 2 .. number и поэтому проверять на делимость дальше не нужно

ведь если число a делится на число b из диапазона number / 2 .. number:

c = a / b

то оно делится и на число c из диапазона 0 ..number / 2

Но это неоптимальный алгоритм, потому что достаточно проверить все числа в диапазоне 2 .. sqrt(number) и если число не делится ни на одно число из этого диапазона, то оно простое.

На этом принципе основано решето Эратосфена поиска простых чисел — когда вы рассматриваете только sqrt(n) чисел чтобы найти все простые числа до n

P.S.

по хорошему надо проверить делимость на 2, а дальше в диапазоне проверять только нечётные числа

а еще как только найден делитель — не надо проверять остальные числа и так понятно, что число составное и можно выходить

def is_prime(number):
    if number % 2 == 0:
        return number == 2

    # Локальные переменные
    sqrt_num = int(number**.5)

    for count in range(3, sqrt_num + 1, 2):
        if number % count == 0:
            return False
        
    return True

Простое число — это целое положительное число, имеющее ровно два различных натуральных делителя — единицу и самого себя. Определение того является ли число простым или нет — это одна из самых распространенных задач, решаемых в рамках курса лабораторных работ по информатике. Ниже будет представлена реализация алгоритма поиска простых чисел в C#, а также использование различных циклов для вывода простых чисел.

Задача №1

Проверить является ли число простым и вывести результат вычисления в консоль.

Алгоритм определения простого числа

Для того, чтобы проверить является ли число N простым необходимо:

1. Задаем значение N
2. Задаем цикл for от 2 до N-1 (счётчик цикла обозначим, например, как i)
   1. Если остаток от деление N на i равен нулю, то число не является простым — выходим из цикла
   2. Если остаток от деления N на i не равен нулю, то переходим к следующей итерации цикла
3. Если цикл полностью пройден, то число является простым.

Метод определения простого числа в C#, реализующий представленный выше алгоритм может быть представлен следующим образом:

public bool IsPrime(int number)
{
    for (int i = 2; i < number; i++)
    {
        if (number % i == 0)
            return false;
    }
    return true;
}

Пример определения простых чисел из диапазона от 1 до N

Если по условиям задачи конечное значение диапазона задается в виде числа N, то здесь удобно использовать цикл for или while. Пример программы с использованием цикла for представлен ниже:

using System;

namespace Prime
{
    class Program
    {
        public static bool IsPrime(int number) 
        { 
            for (int i = 2; i < number; i++) 
            { 
                if (number % i == 0) 
                    return false; 
            } 
            return true; 
        }

        static void Main(string[] args)
        {
            Console.WriteLine("Введите конечное значение диапазона 1...N и нажмите Enter");
            Console.WriteLine("N = "); 
            if ((!int.TryParse(Console.ReadLine(), out int result))||(result<0))
                Console.WriteLine("Число должно быть положительным и целым");
            Console.WriteLine($"Простые числа из диапазона от 1 до {result}");
            int count = 0;
            for (int i = 1; i <= result; i++)
            {
                if (IsPrime(i))
                {
                    Console.Write($"{i} ");
                    count++;
                }
            }
            Console.WriteLine("");
            Console.WriteLine($"Найдено {count} простых чисел из диапазона от 1 до {result}");
        }
    }
}

Строго говоря, число 1 не является ни простым не составным, поэтому его можно было бы исключить из цикла, что мы и сделаем в следующем примере.

Пример определения заданного количества простых чисел

Задача поиска простых чисел может быть сформулирована и по другому, например, так: найти первые N простых чисел. В этом случае нам будет выгодно использовать цикл while:

using System;

namespace Prime
{
    class Program
    {
        public static bool IsPrime(int number) 
        { 
            for (int i = 2; i < number; i++) 
            { 
                if (number % i == 0) 
                    return false; 
            } 
            return true; 
        }

        static void Main(string[] args)
        {
            Console.WriteLine("Введите количество простых чисел которые необходимо найти");
            Console.WriteLine("N = "); 
            if ((!int.TryParse(Console.ReadLine(), out int result))||(result<=0))
                Console.WriteLine("Число должно быть положительным и целым");
            Console.WriteLine($"Первые {result} простых чисел");
            int count = 0; //количество найденных простых чисел
            int number = 1; //очередное число, проверку которого необходимо найти
            int total = 0; //общее количество проверенных чисел
            while (count<result)
            {
                total++;
                number++;
                if (IsPrime(number))
                {
                    Console.Write($"{number} ");
                    count++;
                }
            }
            Console.WriteLine("");
            Console.WriteLine($"Найдено {count} простых чисел. Проверено {total} чисел");
        }
    }
}

Результатом работы программы будет вывод в консоль первых N простых чисел.

Итого

Сегодня мы рассмотрели алгоритм поиска простых чисел и реализовали этот алгоритм в C#. В зависимости от условий задачи, мы использовали различные виды циклов для поиска набора простых чисел.