Рубрики

Тест на первичность | Комплект 1 (Введение и школьный метод)

Учитывая положительное целое число, проверьте, является ли число простым или нет. Простое число — это натуральное число, большее 1, которое не имеет положительных делителей, кроме 1 и самого себя. Примеры первых нескольких простых чисел: {2, 3, 5,

Примеры :

Input:  n = 11
Output: true

Input:  n = 15
Output: false

Input:  n = 1
Output: false

Школьный метод
Простое решение состоит в том, чтобы перебрать все числа от 2 до n-1 и для каждого числа проверить, делит ли оно n. Если мы найдем любое число, которое делит, мы вернем false.

Ниже приведена реализация этого метода.

C ++

// Школьная программа на C ++ для проверки,
// число простое
#include <bits/stdc++.h>

using namespace std;

  

bool isPrime(int n)

{

    // Угловой корпус

    if (n <= 1)  return false;

  

    // Проверка от 2 до n-1

    for (int i=2; i<n; i++)

        if (n%i == 0)

            return false;

  

    return true;

}

  
// Программа драйвера для проверки вышеуказанной функции

int main()

{

    isPrime(11)?  cout << " true\n": cout << " false\n";

    isPrime(15)?  cout << " true\n": cout << " false\n";

    return 0;

}

Джава

// Школьная программа на основе JAVA
// проверить, является ли число простым

class GFG {

      

    static boolean isPrime(int n)

    {

        // Угловой корпус

        if (n <= 1) return false;

      

        // Проверка от 2 до n-1

        for (int i = 2; i < n; i++)

            if (n % i == 0)

                return false;

      

        return true;

    }

      

    // Программа для водителя

    public static void main(String args[])

    {

        if(isPrime(11))

            System.out.println(" true");

        else

            System.out.println(" false");

        if(isPrime(15))

            System.out.println(" true");

        else

            System.out.println(" false");

          

    }

}

  
// Этот код добавлен
// Никита Тивари.

python3

# Школьный метод на основе Python3
# программа для проверки номера
# простое

  

def isPrime(n):

  

    # Угловой кейс

    if n <= 1:

        return False

  

    # Проверка от 2 до n-1

    for i in range(2, n):

        if n % i == 0:

            return False;

  

    return True

  
Программа # Driver для проверки вышеуказанной функции

print("true") if isPrime(11) else print("false")

print("true") if isPrime(14) else print("false")

  
# Этот код предоставлен Смитой Динеш Семвал

C #

// Оптимизированный школьный метод на основе C #
// программа для проверки, является ли число простым

using System;

  

namespace prime

{

    public class GFG

    {     

        public static bool isprime(int n)

        {

            // Угловые шкафы

            if (n <= 1) return false;

              

            for (int i = 2; i < n; i++)

                if (n % i == 0)

                return false;

   

            return true;

        }

          

        // Драйвер программы

        public static void Main()

        {

            if (isprime(11)) Console.WriteLine("true");

            else Console.WriteLine("false");

              

            if (isprime(15)) Console.WriteLine("true");

            else Console.WriteLine("false");

        }

    }

}

  
// Этот код предоставлен Sam007

PHP

<?php
// Школьный метод на основе PHP
// программа для проверки номера
// простое

  

function isPrime($n)

{

    // Угловой корпус

    if ($n <= 1) return false;

  

    // Проверка от 2 до n-1

    for ($i = 2; $i < $n; $i++)

        if ($n % $i == 0)

            return false;

  

    return true;

}

  
// Код драйвера

$tet = isPrime(11) ? " true\n"

                     " false\n";

echo $tet;

$tet = isPrime(15) ? " true\n"

                     " false\n";

echo $tet;

  
// Этот код предоставлен m_kit
?>


Выход :

true
false

Временная сложность этого решения составляет O (n)

Оптимизированный школьный метод
Мы можем сделать следующие оптимизации:

  1. Вместо проверки до n, мы можем проверить до √n, потому что больший коэффициент n должен быть кратным меньшему коэффициенту, который уже был проверен.
  2. Алгоритм может быть улучшен дополнительно, наблюдая, что все простые числа имеют форму 6k ± 1, за исключением 2 и 3. Это потому, что все целые числа могут быть выражены как (6k + i) для некоторого целого числа k и для i = — 1, 0, 1, 2, 3 или 4; 2 делит (6k + 0), (6k + 2), (6k + 4); и 3 делит (6k + 3). Таким образом, более эффективный метод состоит в том, чтобы проверить, делится ли n на 2 или 3, а затем проверить все числа в форме 6k ± 1. (Источник: Википедия )
  3. Ниже приведена реализация этого решения.

    C ++

    // Оптимизированная школьная программа на C ++ для проверки
    // если число простое
    #include <bits/stdc++.h>

    using namespace std;

      

    bool isPrime(int n)

    {

        // Угловые шкафы

        if (n <= 1)  return false;

        if (n <= 3)  return true;

      

        // Это проверено, чтобы мы могли пропустить

        // средние пять чисел в нижнем цикле

        if (n%2 == 0 || n%3 == 0) return false;

      

        for (int i=5; i*i<=n; i=i+6)

            if (n%i == 0 || n%(i+2) == 0)

               return false;

      

        return true;

    }

      

      
    // Программа драйвера для проверки вышеуказанной функции

    int main()

    {

        isPrime(11)?  cout << " true\n": cout << " false\n";

        isPrime(15)?  cout << " true\n": cout << " false\n";

        return 0;

    }

    Джава

    // Оптимизированный школьный метод на основе Java
    // программа для проверки, является ли число простым

    import java.io.*;

      

    class GFG {

          

        static boolean isPrime(int n)

        {

            // Угловые шкафы

            if (n <= 1) return false;

            if (n <= 3) return true;

          

            // Это проверено, чтобы мы могли пропустить

            // средние пять чисел в нижнем цикле

            if (n % 2 == 0 || n % 3 == 0) return false;

          

            for (int i = 5; i * i <= n; i = i + 6)

                if (n % i == 0 || n % (i + 2) == 0)

                return false;

          

            return true;

        }

      

      

        // Программа для водителя

        public static void main(String args[])

        {

            if(isPrime(11))

                System.out.println(" true");

            else

                System.out.println(" false");

            if(isPrime(15))

                System.out.println(" true");

            else

                System.out.println(" false");

              

        }

    }

      
    / * Этот код предоставлен Никитой Тивари. * /

    python3

    # Оптимизированный школьный метод на основе
    # Python3 программа для проверки
    # если число простое

      

      

    def isPrime(n) :

        # Угловые чехлы

        if (n <= 1) :

            return False

        if (n <= 3) :

            return True

      

        # Это проверено, чтобы мы могли пропустить

        # средние пять чисел в нижнем цикле

        if (n % 2 == 0 or n % 3 == 0) :

            return False

      

        i = 5

        while(i * i <= n) :

            if (n % i == 0 or n % (i + 2) == 0) :

                return False

            i = i + 6

      

        return True

      

      
    # Драйверная программа

      

    if(isPrime(11)) :

        print(" true")

    else :

        print(" false")

          

    if(isPrime(15)) :

        print(" true")

    else

        print(" false")

          

          
    # Этот код добавлен
    # Никита Тивари.

    C #

    // Оптимизированный школьный метод на основе C #
    // программа для проверки, является ли число простым

    using System;

      

    class GFG

    {

        public static bool isPrime(int n)

        {

            // Угловые шкафы

            if (n <= 1) return false;

            if (n <= 3) return true;

          

            // Это проверено, чтобы мы

            // можем пропустить средние пять чисел

            // в нижнем цикле

            if (n % 2 == 0 || n % 3 == 0) return false;

          

            for (int i = 5; i * i <= n; i = i + 6)

                if (n % i == 0 || n % (i + 2) == 0)

                return false;

          

            return true;

        }

          

        // Код драйвера

        public static void Main()

        {

                if (isPrime(11)) Console.WriteLine("true");

                else Console.WriteLine("false");

                  

                if (isPrime(15)) Console.WriteLine("true");

                else Console.WriteLine("false");

        }

    }

      
    // Этот код предоставлен aj_36

             

    PHP

    <?php
    // Оптимизированный школьный метод
    // основанная программа PHP для проверки
    // если число простое

      

    function isPrime($n)

    {

          

        // Угловые шкафы

        if ($n <= 1) 

            return false;

        if ($n <= 3) 

            return true;

      

        // Это проверено, чтобы мы могли пропустить

        // средние пять чисел в нижнем цикле

        if ($n % 2 == 0 || $n % 3 == 0) 

            return false;

      

        for($i = 5; $i * $i <= $n; $i = $i + 6)

            if ($n % $i == 0 || $n % ($i + 2) == 0)

            return false;

      

        return true;

    }

      

        // Код драйвера

        if(isPrime(11))

            echo " true\n";

        else

            echo " false\n";

              

        if(isPrime(15))

            echo " true\n";

        else

            echo " false\n";

      
    // Этот код предоставлен ajit
    ?>


    Выход :

    true
    false
    

    Временная сложность этого решения составляет O (√n)

    Тест на первичность | Набор 2 (метод Ферма)

    Ссылки:
    https://en.wikipedia.org/wiki/Prime_number
    http://www.cse.iitk.ac.in/users/manindra/presentations/FLTBasedTests.pdf
    https://en.wikipedia.org/wiki/Primality_test

    Эта статья предоставлена Ajay . Пожалуйста, напишите комментарии, если вы обнаружите что-то неправильное, или вы хотите поделиться дополнительной информацией по обсуждаемой теме

    Рекомендуемые посты:

    Тест на первичность | Комплект 1 (Введение и школьный метод)

    0.00 (0%) 0 votes