Рубрики

Найдите самых маленьких близнецов в заданном диапазоне

Для заданного диапазона [low..high] выведите наименьшее число близнецов в заданном диапазоне (включительно низкое и высокое). Два числа — близнецы, если они простые, и разница равна 2.

Пример:

Input:  low = 10,  high = 100
Output: Smallest twins in given range: (11, 13)
Both 11 and 13 are prime numbers and difference 
between them is two, therefore twins.  And these
are the smallest twins in [10..100]

Input:  low = 50,  high = 100
Output: Smallest twins in given range: (59, 61) 

Простое решение состоит в том, чтобы начать с низкого уровня и для каждого числа x проверить, не являются ли x и x + 2 простыми числами. Здесь х варьируется от низкого до высокого-2.

Эффективным решением является использование сита эратосфена

1) Create a boolean array "prime[0..high]" and initialize all 
   entries in it as true. A value in prime[i] will finally 
   be false if i is not a prime number, else true.

2) Run a loop from p = 2 to high. 
    a) If prime[p] is true, then p is prime. [See this]
    b) Mark all multiples of p as not prime in prime[]. 

3) Run a loop from low to high and print the first twins
   using prime[] built in step 2.   

Ниже приведена реализация вышеуказанной идеи.

C ++

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

using namespace std; 

  

void printTwins(int low, int high) 

    // Создаем логический массив "prime [0..high]" и инициализируем

    // все записи это как правда. Значение в простом [i] будет, наконец,

    // быть ложным, если я не простое число, иначе верно.

    bool prime[high+1], twin = false

    memset(prime, true, sizeof(prime)); 

  

    prime[0] = prime[1] = false

  

    // ищем самого маленького близнеца

    for (int p=2; p<=floor(sqrt(high))+1; p++) 

    

        // Если p не отмечено, то это простое число

        if (prime[p]) 

        

            // Обновить все кратные р

            for (int i=p*2; i<=high; i += p) 

                prime[i] = false

        

    

  

    // Теперь печатаем самый маленький близнец в диапазоне

    for (int i=low; i<=high; i++) 

    

        if (prime[i] && prime[i+2]) 

        

            cout << "Smallest twins in given range: ("

                << i << ", " << i+2 << ")"

            twin = true;

            break

        

    

      

    if (twin == false)

      cout << "No such pair exists" <<endl;

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

int main() 

    printTwins(10, 100); 

    return 0; 

Джава

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

  

class GFG {

  

    static void printTwins(int low, int high) {

        // Создаем логический массив "prime [0..high]" и инициализируем

        // все записи это как правда. Значение в простом [i] будет, наконец,

        // быть ложным, если я не простое число, иначе верно.

        boolean prime[] = new boolean[high + 1], twin = false;

        for (int i = 0; i < prime.length; i++) {

            prime[i] = true;

        }

  

        prime[0] = prime[1] = false;

  

        // ищем самого маленького близнеца

        for (int p = 2; p <= Math.floor(Math.sqrt(high)) + 1; p++) {

            // Если p не отмечено, то это простое число

            if (prime[p]) {

                // Обновить все кратные р

                for (int i = p * 2; i <= high; i += p) {

                    prime[i] = false;

                }

            }

        }

  

        // Теперь печатаем самый маленький близнец в диапазоне

        for (int i = low; i <= high; i++) {

            if (prime[i] && prime[i + 2]) {

                int a = i + 2 ;

                System.out.print("Smallest twins in given range: ("

                        + i + ", " + a + ")");

                twin = true;

                break;

            }

        }

  

        if (twin == false) {

            System.out.println("No such pair exists");

        }

    }

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

    public static void main(String[] args) {

  

        printTwins(10, 100);

    }

}
// Этот код предоставлен Rajput-Ji

python3

# Python3 программа для поиска самых маленьких
# близнец в заданном диапазоне

import math

  

def printTwins(low, high): 

  

    # Создайте логический массив "prime [0..high]"

    # и инициализировать все записи как true.

    # Значение в простом [i], наконец, будет

    # ложь, если я не простое число, иначе верно.

    prime = [True] * (high + 1);

    twin = False

  

    prime[0] = prime[1] = False

  

    # Ищите самого маленького близнеца

    for p in range(2, int(math.floor(

                          math.sqrt(high)) + 2)):

          

        # Если p не отмечено, то оно

        # простое число

        if (prime[p]): 

              

            # Обновить все кратные р

            for i in range(p * 2, high + 1, p): 

                prime[i] = False

  

    # Теперь напечатайте самый маленький близнец в диапазоне

    for i in range(low, high + 1): 

        if (prime[i] and prime[i + 2]): 

            print("Smallest twins in given range: ("

                               i, ",", (i + 2), ")"); 

            twin = True;

            break

      

    if (twin == False):

        print("No such pair exists");

  
Код водителя

printTwins(10, 100); 

      
# Этот код добавлен
# by chandan_jnu

C #

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

  

using System; 

public class GFG {

   

    static void printTwins(int low, int high) {

        // Создаем логический массив "prime [0..high]" и инициализируем

        // все записи это как правда. Значение в простом [i] будет, наконец,

        // быть ложным, если я не простое число, иначе верно.

        bool []prime = new bool[high + 1]; bool twin = false;

        for (int i = 0; i < prime.Length; i++) {

            prime[i] = true;

        }

   

        prime[0] = prime[1] = false;

   

        // ищем самого маленького близнеца

        for (int p = 2; p <= Math.Floor(Math.Sqrt(high)) + 1; p++) {

            // Если p не отмечено, то это простое число

            if (prime[p]) {

                // Обновить все кратные р

                for (int i = p * 2; i <= high; i += p) {

                    prime[i] = false;

                }

            }

        }

   

        // Теперь печатаем самый маленький близнец в диапазоне

        for (int i = low; i <= high; i++) {

            if (prime[i] && prime[i + 2]) {

                int a = i + 2 ;

                Console.Write("Smallest twins in given range: ("

                        + i + ", " + a + ")");

                twin = true;

                break;

            }

        }

   

        if (twin == false) {

            Console.WriteLine("No such pair exists");

        }

    }

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

    public static void Main() {

   

        printTwins(10, 100);

    }

}
// этот код предоставлен Rajput-Ji

PHP

<?php
// PHP программа для поиска самых маленьких
// близнец в заданном диапазоне

  

function printTwins($low, $high

    // Создаем логический массив "prime [0..high]"

    // и инициализируем все записи как true.

    // Значение в простом [i] будет наконец

    // false если я не простое число, иначе true.

    $prime = array_fill(0, $high + 1, true);

    $twin = false; 

  

    $prime[0] = $prime[1] = false; 

  

    // ищем самого маленького близнеца

    for ($p = 2; $p <= floor(sqrt($high)) + 1; $p++) 

    

        // Если p не отмечено, то это простое число

        if ($prime[$p]) 

        

            // Обновить все кратные р

            for ($i = $p * 2; $i <= $high; $i += $p

                $prime[$i] = false; 

        

    

  

    // Теперь печатаем самый маленький близнец в диапазоне

    for ($i = $low; $i <= $high; $i++) 

    

        if ($prime[$i] && $prime[$i + 2]) 

        

            print("Smallest twins in given range: ($i, "

                                          ($i + 2). ")"); 

            $twin = true;

            break

        

    

      

    if ($twin == false)

    print("No such pair exists\n");

  
// Код драйвера
printTwins(10, 100); 

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

Выход:

Smallest twins in given range: (11, 13)

Спасибо Уткаршу Триведи за предложение об этом решении.

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

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

Найдите самых маленьких близнецов в заданном диапазоне

0.00 (0%) 0 votes