Рубрики

Ближайшее простое число меньше заданного числа n

Вам дано число n (3 <= n <10 ^ 6), и вы должны найти ближайшее простое число меньше n?

Примеры:

Input : n = 10
Output: 7

Input : n = 17
Output: 13

Input : n = 30
Output: 29

Простым решением этой проблемы является итерация от n-1 до 2, и для каждого числа проверьте, является ли оно простым числом. Если простое число, верните его и разорвите цикл. Это решение выглядит хорошо, если есть только один запрос. Но неэффективно, если есть несколько запросов для разных значений n.

Эффективным решением этой проблемы является генерация всех простых чисел меньше 10 ^ 6 с использованием Sieve of Sundaram и сохранение их в массиве в возрастающем порядке. Теперь примените модифицированный бинарный поиск для поиска ближайшего простого числа меньше n. Временная сложность этого решения составляет O (n log n + log n) = O (n log n).

C ++

// C ++ программа для поиска ближайшего простого числа к n.
#include<bits/stdc++.h>
#define MAX 1000000

using namespace std;

  
// массив для хранения всех простых чисел меньше 10 ^ 6

vector<int> primes;

  
// Сервисная функция Сита Сундарама

void Sieve()

{

    int n = MAX;

  

    // В общем сито сундарам, производит простые числа

    // меньше (2 * x + 2) для заданного числа

    // число х

    int nNew = sqrt(n);

  

    // Этот массив используется для разделения номеров

    // формируем i + j + 2ij из других, где 1 <= i <= j

    int marked[n/2+500] = {0};

  

    // удаляем индексы, которые не дают простых чисел

    for (int i=1; i<=(nNew-1)/2; i++)

        for (int j=(i*(i+1))<<1; j<=n/2; j=j+2*i+1)

            marked[j] = 1;

  

    // Поскольку 2 - простое число

    primes.push_back(2);

  

    // Остальные простые числа имеют вид 2 * i + 1 такой

    // то, что помечено [i], ложно.

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

        if (marked[i] == 0)

            primes.push_back(2*i + 1);

}

  
// модифицированный бинарный поиск для поиска ближайшего простого числа меньше N

int binarySearch(int left,int right,int n)

{

    if (left<=right)

    {

        int mid = (left + right)/2;

  

        // базовое условие, если мы достигаем слева

        // угол или правый угол массива простых чисел

        // вернуть этот угловой элемент, потому что до или

        // после этого у нас нет простого числа в

        // массив простых чисел

        if (mid == 0 || mid == primes.size()-1)

            return primes[mid];

  

        // теперь, если n само по себе простое число, оно будет присутствовать

        // в массиве простых чисел и здесь мы должны найти ближайший

        // простое число меньше n, поэтому мы вернем простые числа [mid-1]

        if (primes[mid] == n)

            return primes[mid-1];

  

        // теперь, если простые [mid] <n и простые [mid + 1]> n то

        // означает, что мы достигли ближайшего простого

        if (primes[mid] < n && primes[mid+1] > n)

            return primes[mid];

        if (n < primes[mid])

            return binarySearch(left, mid-1, n);

        else

            return binarySearch(mid+1, right, n);

    }

    return 0;

}

  
// Драйвер программы для запуска дела

int main()

{

    Sieve();

    int n = 17;

    cout << binarySearch(0, primes.size()-1, n);

    return 0;

}

Джава

// Java-программа для поиска ближайшего простого числа к n.

import java.util.*;

  

class GFG

{

      

static int MAX=1000000;

  
// массив для хранения всех простых чисел меньше 10 ^ 6

static ArrayList<Integer> primes = new ArrayList<Integer>();

  
// Сервисная функция Сита Сундарама

static void Sieve()

{

    int n = MAX;

  

    // В общем сито сундарам, производит простые числа

    // меньше (2 * x + 2) для заданного числа

    // число х

    int nNew = (int)Math.sqrt(n);

  

    // Этот массив используется для разделения номеров

    // формируем i + j + 2ij из других, где 1 <= i <= j

    int[] marked = new int[n / 2 + 500];

  

    // удаляем индексы, которые не дают простых чисел

    for (int i = 1; i <= (nNew - 1) / 2; i++)

        for (int j = (i * (i + 1)) << 1

                j <= n / 2; j = j + 2 * i + 1)

            marked[j] = 1;

  

    // Поскольку 2 - простое число

    primes.add(2);

  

    // Остальные простые числа имеют вид 2 * i + 1 такой

    // то, что помечено [i], ложно.

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

        if (marked[i] == 0)

            primes.add(2 * i + 1);

}

  
// модифицированный бинарный поиск для поиска ближайшего простого числа меньше N

static int binarySearch(int left,int right,int n)

{

    if (left <= right)

    {

        int mid = (left + right) / 2;

  

        // базовое условие, если мы достигаем слева

        // угол или правый угол массива простых чисел

        // вернуть этот угловой элемент, потому что до или

        // после этого у нас нет простого числа в

        // массив простых чисел

        if (mid == 0 || mid == primes.size() - 1)

            return primes.get(mid);

  

        // теперь, если n само по себе простое число, оно будет присутствовать

        // в массиве простых чисел и здесь мы должны найти ближайший

        // простое число меньше n, поэтому мы вернем простые числа [mid-1]

        if (primes.get(mid) == n)

            return primes.get(mid - 1);

  

        // теперь, если простые [mid] <n и простые [mid + 1]> n то

        // означает, что мы достигли ближайшего простого

        if (primes.get(mid) < n && primes.get(mid + 1) > n)

            return primes.get(mid);

        if (n < primes.get(mid))

            return binarySearch(left, mid - 1, n);

        else

            return binarySearch(mid + 1, right, n);

    }

    return 0;

}

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

public static void main (String[] args) 

{

    Sieve();

    int n = 17;

    System.out.println(binarySearch(0,

                        primes.size() - 1, n));

}
}

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

python3

# Python3 программа для поиска ближайшего
# премьер к п.

import math

MAX = 10000;

  
# массив для хранения всех простых чисел меньше
# 10 ^ 6

primes = [];

  
# Полезная функция Сита Сундарама

def Sieve():

  

    n = MAX;

  

    # В общем Сито Сундарам, производит

    # простых чисел меньше (2 * x + 2) для

    # номер заданный номер x

    nNew = int(math.sqrt(n));

  

    # Этот массив используется для разделения чисел

    # вида i + j + 2ij от других, где

    # 1 <= i <= j

    marked = [0] * (int(n / 2 + 500));

  

    # устранить индексы, которые не

    # производить простые числа

    for i in range(1, int((nNew - 1) / 2) + 1):

        for j in range(((i * (i + 1)) << 1), 

                        (int(n / 2) + 1), (2 * i + 1)):

            marked[j] = 1;

  

    # Так как 2 - простое число

    primes.append(2);

  

    # Остальные простые числа имеют вид

    # 2 * i + 1 такой, что помеченный [i] является ложным.

    for i in range(1, int(n / 2) + 1):

        if (marked[i] == 0):

            primes.append(2 * i + 1);

  
# модифицированный бинарный поиск для поиска ближайшего
# простое число меньше чем N

def binarySearch(left, right, n):

    if (left <= right):

        mid = int((left + right) / 2);

  

        # базовое условие, если мы достигаем

        # в левом или правом углу

        # primes [] массив затем вернуть этот угол

        элемент, потому что до или после этого

        # у нас нет простого числа в

        # массив простых чисел

        if (mid == 0 or mid == len(primes) - 1):

            return primes[mid];

  

        # теперь, если n само по себе простое число, оно будет

        # присутствовать в массиве простых чисел и здесь

        # мы должны найти ближайшее простое число меньше

        # n, поэтому мы вернем простые числа [mid-1]

        if (primes[mid] == n):

            return primes[mid - 1];

  

        # теперь, если простые [середина] <n и простые [середина + 1]> n

        # это означает, что мы достигли ближайшего простого

        if (primes[mid] < n and primes[mid + 1] > n):

            return primes[mid];

        if (n < primes[mid]):

            return binarySearch(left, mid - 1, n);

        else:

            return binarySearch(mid + 1, right, n);

  

    return 0;

  
Код водителя
Sieve();

n = 17;

print(binarySearch(0, len(primes) - 1, n));

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

C #

// C # программа для поиска ближайшего простого числа к n.

using System;

using System.Collections;

class GFG

{

      

static int MAX = 1000000;

  
// массив для хранения всех простых чисел меньше 10 ^ 6

static ArrayList primes = new ArrayList();

  
// Сервисная функция Сита Сундарама

static void Sieve()

{

    int n = MAX;

  

    // В общем сито сундарам, производит

    // простые числа меньше (2 * x + 2) для

    // номер заданный номер x

    int nNew = (int)Math.Sqrt(n);

  

    // Этот массив используется для разделения номеров

    // формируем i + j + 2ij из других, где 1 <= i <= j

    int[] marked = new int[n / 2 + 500];

  

    // удаляем индексы, которые не дают простых чисел

    for (int i = 1; i <= (nNew - 1) / 2; i++)

        for (int j = (i * (i + 1)) << 1; 

                 j <= n / 2; j = j + 2 * i + 1)

            marked[j] = 1;

  

    // Поскольку 2 - простое число

    primes.Add(2);

  

    // Остальные простые числа имеют вид 2 * i + 1

    // такой, что отмеченный [i] является ложным.

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

        if (marked[i] == 0)

            primes.Add(2 * i + 1);

}

  
// модифицированный бинарный поиск для поиска
// ближайшее простое меньше N

static int binarySearch(int left, int right, int n)

{

    if (left <= right)

    {

        int mid = (left + right) / 2;

  

        // базовое условие, если мы достигаем слева

        // угол или правый угол массива простых чисел

        // вернуть этот угловой элемент, потому что до или

        // после этого у нас нет простого числа в

        // массив простых чисел

        if (mid == 0 || mid == primes.Count - 1)

            return (int)primes[mid];

  

        // теперь, если n - простое число, оно будет

        // присутствует в массиве простых чисел и здесь мы имеем

        // найти ближайшее простое число меньше n, поэтому мы

        // вернем простые числа [mid-1]

        if ((int)primes[mid] == n)

            return (int)primes[mid - 1];

  

        // теперь, если простые [mid] <n и простые [mid + 1]> n

        // это означает, что мы достигли ближайшего простого

        if ((int)primes[mid] < n &&

            (int)primes[mid + 1] > n)

            return (int)primes[mid];

        if (n < (int)primes[mid])

            return binarySearch(left, mid - 1, n);

        else

            return binarySearch(mid + 1, right, n);

    }

    return 0;

}

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

static void Main() 

{

    Sieve();

    int n = 17;

    Console.WriteLine(binarySearch(0,

                      primes.Count - 1, n));

}
}

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

PHP

<?php
// PHP программа для поиска ближайшего
// простое число до n.

  

$MAX = 10000;

  
// массив для хранения всех простых чисел
// чем 10 ^ 6

$primes = array();

  
// Сервисная функция Сита Сундарама

function Sieve()

{

    global $MAX, $primes;

    $n = $MAX;

  

    // В общем сито сундарам, производит

    // простые числа меньше (2 * x + 2) для

    // номер заданный номер x

    $nNew = (int)(sqrt($n));

  

    // Этот массив используется для разделения чисел

    // вида i + j + 2ij от других, где

    // 1 <= i <= j

    $marked = array_fill(0, (int)($n / 2 + 500), 0);

  

    // исключаем индексы, которые не

    // производим простые числа

    for ($i = 1; $i <= ($nNew - 1) / 2; $i++)

        for ($j = ($i * ($i + 1)) << 1; 

             $j <= $n / 2; $j = $j + 2 * $i + 1)

            $marked[$j] = 1;

  

    // Поскольку 2 - простое число

    array_push($primes, 2);

  

    // Остальные простые числа имеют вид

    // 2 * i + 1 такой, что отмеченный [i] является ложным.

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

        if ($marked[$i] == 0)

            array_push($primes, 2 * $i + 1);

}

  
// модифицированный бинарный поиск для поиска ближайшего
// простое число меньше N

function binarySearch($left, $right, $n)

{

    global $primes;

    if ($left <= $right)

    {

        $mid = (int)(($left + $right) / 2);

  

        // базовое условие, если мы достигаем

        // в левом или правом углу

        // массив primes [] затем возвращает этот угол

        // элемент, потому что до или после этого

        // у нас нет простого числа в

        // массив простых чисел

        if ($mid == 0 || $mid == count($primes) - 1)

            return $primes[$mid];

  

        // теперь, если n само по себе простое число, оно будет

        // присутствовать в массиве простых чисел и здесь

        // мы должны найти ближайшее простое число меньше

        // n, поэтому мы вернем простые числа [mid-1]

        if ($primes[$mid] == $n)

            return $primes[$mid - 1];

  

        // теперь, если простые [mid] <n и простые [mid + 1]> n

        // это означает, что мы достигли ближайшего простого

        if ($primes[$mid] < $n && $primes[$mid + 1] > $n)

            return $primes[$mid];

        if ($n < $primes[$mid])

            return binarySearch($left, $mid - 1, $n);

        else

            return binarySearch($mid + 1, $right, $n);

    }

    return 0;

}

  
// Код драйвера
Sieve();

$n = 17;

echo binarySearch(0, count($primes) - 1, $n);

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


Выход:

13

Если у вас есть другой подход к решению этой проблемы, пожалуйста, поделитесь в комментариях.

Эта статья предоставлена Шашанком Мишрой (Гуллу) . Если вы как GeeksforGeeks и хотели бы внести свой вклад, вы также можете написать статью с помощью contribute.geeksforgeeks.org или по почте статьи contribute@geeksforgeeks.org. Смотрите свою статью, появляющуюся на главной странице GeeksforGeeks, и помогите другим вундеркиндам.

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

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

Ближайшее простое число меньше заданного числа n

0.00 (0%) 0 votes