Рубрики

Программа для поиска следующего простого числа

Математика

Дано целое число N. Задача состоит в том, чтобы найти следующее простое число, т.е. наименьшее простое число, большее N.

Примеры:

Input: N = 10
Output: 11
11 is the smallest prime number greater than 10.

Input: N = 0
Output: 2

Подходить:

  1. Прежде всего, возьмите найденную логическую переменную и инициализируйте ее как false.
  2. Теперь, пока эта переменная не равна true, увеличивайте N на 1 в каждой итерации и проверяйте, является ли она простой или нет.
  3. Если оно простое, то выведите его и измените значение найденной переменной на True. в противном случае повторяйте цикл, пока не получите следующее простое число.

Ниже приведена реализация вышеуказанного подхода:

C ++

// C ++ реализация подхода
#include <bits/stdc++.h>

using namespace std;

  
// Функция, которая возвращает true, если n
// простое число возвращает false

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; 

} 

  
// Функция для возврата наименьшего
// простое число больше чем N

int nextPrime(int N)

{

  

    // Базовый вариант

    if (N <= 1)

        return 2;

  

    int prime = N;

    bool found = false;

  

    // Цикл непрерывно, пока не вернется isPrime

    // истина для числа больше n

    while (!found) {

        prime++;

  

        if (isPrime(prime))

            found = true;

    }

  

    return prime;

}

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

int main()

{

    int N = 3;

  

    cout << nextPrime(N);

  

    return 0;

}

Джава

// Java реализация подхода

class GFG 

{

  

    // Функция, которая возвращает true, если n

    // простое число возвращает false

    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; 

    } 

      

    // Функция для возврата наименьшего

    // простое число больше чем N

    static int nextPrime(int N) 

    { 

      

        // Базовый вариант

        if (N <= 1) 

            return 2; 

      

        int prime = N; 

        boolean found = false; 

      

        // Цикл непрерывно, пока не вернется isPrime

        // истина для числа больше n

        while (!found) 

        { 

            prime++; 

      

            if (isPrime(prime)) 

                found = true; 

        } 

      

        return prime; 

    } 

      

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

    public static void main (String[] args)

    { 

        int N = 3; 

      

        System.out.println(nextPrime(N)); 

    } 

}

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

python3

# Python3 реализация подхода

import math

  
# Функция, которая возвращает True, если n
# простое число возвращает False

def isPrime(n):

      

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

    if(n <= 1):

        return False

    if(n <= 3):

        return True

      

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

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

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

        return False

      

    for i in range(5,int(math.sqrt(n) + 1), 6): 

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

            return False

      

    return True

  
# Функция для возврата наименьшего
# простое число больше чем N

def nextPrime(N):

  

    # Базовый вариант

    if (N <= 1):

        return 2

  

    prime = N

    found = False

  

    # Цикл непрерывно, пока не вернется isPrime

    # Правда для числа больше n

    while(not found):

        prime = prime + 1

  

        if(isPrime(prime) == True):

            found = True

  

    return prime

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

N = 3

print(nextPrime(N))

  
# Этот код предоставлен Sanjit_Prasad

C #

// C # реализация подхода

using System;

      

class GFG 

{

  

    // Функция, которая возвращает true, если n

    // простое число возвращает false

    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; 

    } 

      

    // Функция для возврата наименьшего

    // простое число больше чем N

    static int nextPrime(int N) 

    { 

      

        // Базовый вариант

        if (N <= 1) 

            return 2; 

      

        int prime = N; 

        bool found = false; 

      

        // Цикл непрерывно до isPrime

        // возвращает true для числа

        // больше чем n

        while (!found) 

        { 

            prime++; 

      

            if (isPrime(prime)) 

                found = true; 

        } 

        return prime; 

    } 

      

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

    public static void Main (String[] args)

    { 

        int N = 3; 

      

        Console.WriteLine(nextPrime(N)); 

    } 

}

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

Выход:

5

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

Программа для поиска следующего простого числа

0.00 (0%) 0 votes