Junior Proger

Готовые решения

Программа поиска K-го по счету простого числа

В поиске простых чисел заключается фундаментальная задача в математике и информатике. Простые числа – это натуральные числа, большие единицы, которые имеют всего два делителя: 1 и само число. Их уникальные свойства и важность в криптографии, алгоритмах и многих других областях делают их объектом постоянного интереса и исследований. В данной статье мы представим программу для поиска K-го по счету простого числа.

Теория

Алгоритм поиска K-го по счету простого числа можно реализовать следующим образом:

  • Начнем счет с 2, который является первым простым числом.
  • Проверим, является ли текущее число простым. Для этого можно использовать различные методы проверки на простоту, например, проверку на делимость на все числа от 2 до квадратного корня из текущего числа. Однако для оптимизации производительности лучше использовать алгоритм «Решето Эратосфена» или «Решето Аткина», особенно при больших значениях K.
  • Если текущее число является простым, увеличиваем счетчик простых чисел на 1.
  • Если счетчик достиг значения K, то текущее число — K-е по счету простое число.
  • В противном случае, увеличиваем текущее число на 1 и переходим к шагу 2.

C++

Пример программы на C++, которая находит K-е по счету простое число:

#include <iostream>

// Функция для проверки, является ли число простым
bool isPrime(int num) {
    if (num <= 1) return false;
    if (num <= 3) return true;
    if (num % 2 == 0 || num % 3 == 0) return false;
    
    for (int i = 5; i * i <= num; i += 6) {
        if (num % i == 0 || num % (i + 2) == 0) {
            return false;
        }
    }
    return true;
}

// Функция для нахождения K-го простого числа
int findKthPrime(int k) {
    if (k == 1) return 2; // Первое простое число
    int count = 1;
    int num = 3; // Начнем с проверки нечетных чисел, так как 2 - первое простое число

    while (count < k) {
        if (isPrime(num)) {
            count++;
        }
        if (count == k) {
            return num;
        }
        num += 2; // Переходим к следующему нечетному числу
    }
    return -1; // Если не удалось найти K-е простое число
}

int main() {
    int k;
    std::cout << "Введите значение K: ";
    std::cin >> k;

    if (k < 1) {
        std::cout << "K должно быть больше или равно 1." << std::endl;
    } else {
        int kthPrime = findKthPrime(k);
        if (kthPrime != -1) {
            std::cout << "K-е по счету простое число: " << kthPrime << std::endl;
        } else {
            std::cout << "Не удалось найти K-е простое число." << std::endl;
        }
    }

    return 0;
}

Эта программа использует функцию isPrime для проверки, является ли число простым, и функцию findKthPrime, чтобы найти K-е простое число. Пользователь вводит значение K, и программа выводит K-е по счету простое число.

C#

using System;

class Program
{
    // Функция для проверки, является ли число простым
    static bool IsPrime(int num)
    {
        if (num <= 1) return false;
        if (num <= 3) return true;
        if (num % 2 == 0 || num % 3 == 0) return false;

        for (int i = 5; i * i <= num; i += 6)
        {
            if (num % i == 0 || num % (i + 2) == 0)
            {
                return false;
            }
        }
        return true;
    }

    // Функция для нахождения K-го простого числа
    static int FindKthPrime(int k)
    {
        if (k == 1) return 2; // Первое простое число
        int count = 1;
        int num = 3; // Начнем с проверки нечетных чисел, так как 2 - первое простое число

        while (count < k)
        {
            if (IsPrime(num))
            {
                count++;
            }
            if (count == k)
            {
                return num;
            }
            num += 2; // Переходим к следующему нечетному числу
        }
        return -1; // Если не удалось найти K-е простое число
    }

    static void Main(string[] args)
    {
        Console.Write("Введите значение K: ");
        if (int.TryParse(Console.ReadLine(), out int k) && k > 0)
        {
            int kthPrime = FindKthPrime(k);
            if (kthPrime != -1)
            {
                Console.WriteLine($"K-е по счету простое число: {kthPrime}");
            }
            else
            {
                Console.WriteLine("Не удалось найти K-е простое число.");
            }
        }
        else
        {
            Console.WriteLine("K должно быть целым положительным числом.");
        }
    }
}

Python

def is_prime(num):
    if num <= 1:
        return False
    if num <= 3:
        return True
    if num % 2 == 0 or num % 3 == 0:
        return False

    i = 5
    while i * i <= num:
        if num % i == 0 or num % (i + 2) == 0:
            return False
        i += 6

    return True

def find_kth_prime(k):
    if k == 1:
        return 2  # Первое простое число
    count = 1
    num = 3  # Начнем с проверки нечетных чисел, так как 2 - первое простое число

    while count < k:
        if is_prime(num):
            count += 1
        if count == k:
            return num
        num += 2  # Переходим к следующему нечетному числу

    return -1  # Если не удалось найти K-е простое число

if __name__ == "__main__":
    try:
        k = int(input("Введите значение K: "))
        if k > 0:
            kth_prime = find_kth_prime(k)
            if kth_prime != -1:
                print(f"K-е по счету простое число: {kth_prime}")
            else:
                print("Не удалось найти K-е простое число.")
        else:
            print("K должно быть целым положительным числом.")
    except ValueError:
        print("Ошибка: Введите целое число для K.")

Java

import java.util.Scanner;

public class KthPrimeNumber {
    // Функция для проверки, является ли число простым
    static boolean isPrime(int num) {
        if (num <= 1) return false;
        if (num <= 3) return true;
        if (num % 2 == 0 || num % 3 == 0) return false;

        for (int i = 5; i * i <= num; i += 6) {
            if (num % i == 0 || num % (i + 2) == 0) {
                return false;
            }
        }
        return true;
    }

    // Функция для нахождения K-го простого числа
    static int findKthPrime(int k) {
        if (k == 1) return 2; // Первое простое число
        int count = 1;
        int num = 3; // Начнем с проверки нечетных чисел, так как 2 - первое простое число

        while (count < k) {
            if (isPrime(num)) {
                count++;
            }
            if (count == k) {
                return num;
            }
            num += 2; // Переходим к следующему нечетному числу
        }
        return -1; // Если не удалось найти K-е простое число
    }

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        System.out.print("Введите значение K: ");

        if (scanner.hasNextInt()) {
            int k = scanner.nextInt();

            if (k > 0) {
                int kthPrime = findKthPrime(k);
                if (kthPrime != -1) {
                    System.out.println("K-е по счету простое число: " + kthPrime);
                } else {
                    System.out.println("Не удалось найти K-е простое число.");
                }
            } else {
                System.out.println("K должно быть целым положительным числом.");
            }
        } else {
            System.out.println("Ошибка: Введите целое число для K.");
        }

        scanner.close();
    }
}

Pascal

program KthPrimeNumber;

function IsPrime(num: Integer): Boolean;
var
  i: Integer;
begin
  if num <= 1 then
    IsPrime := False
  else if (num <= 3) then
    IsPrime := True
  else if (num mod 2 = 0) or (num mod 3 = 0) then
    IsPrime := False
  else
  begin
    i := 5;
    while (i * i <= num) do
    begin
      if (num mod i = 0) or (num mod (i + 2) = 0) then
      begin
        IsPrime := False;
        Exit;
      end;
      i := i + 6;
    end;
    IsPrime := True;
  end;
end;

function FindKthPrime(K: Integer): Integer;
var
  count, num: Integer;
begin
  if K = 1 then
    FindKthPrime := 2
  else
  begin
    count := 1;
    num := 3;
    while count < K do
    begin
      if IsPrime(num) then
        count := count + 1;
      if count = K then
      begin
        FindKthPrime := num;
        Exit;
      end;
      num := num + 2;
    end;
    FindKthPrime := -1;  // Если не удалось найти K-е простое число
  end;
end;

var
  K, KthPrime: Integer;
begin
  Write('Введите значение K: ');
  Readln(K);

  if K > 0 then
  begin
    KthPrime := FindKthPrime(K);
    if KthPrime <> -1 then
      Writeln('K-е по счету простое число: ', KthPrime)
    else
      Writeln('Не удалось найти K-е простое число.');
  end
  else
    Writeln('K должно быть целым положительным числом.');
end.

JavaScript

function isPrime(num) {
    if (num <= 1) return false;
    if (num <= 3) return true;
    if (num % 2 === 0 || num % 3 === 0) return false;

    for (let i = 5; i * i <= num; i += 6) {
        if (num % i === 0 || num % (i + 2) === 0) {
            return false;
        }
    }
    return true;
}

function findKthPrime(k) {
    if (k === 1) return 2; // Первое простое число
    let count = 1;
    let num = 3; // Начнем с проверки нечетных чисел, так как 2 - первое простое число

    while (count < k) {
        if (isPrime(num)) {
            count++;
        }
        if (count === k) {
            return num;
        }
        num += 2; // Переходим к следующему нечетному числу
    }
    return -1; // Если не удалось найти K-е простое число
}

const k = prompt("Введите значение K:");

if (k !== null && !isNaN(k) && k > 0) {
    const kthPrime = findKthPrime(parseInt(k));
    if (kthPrime !== -1) {
        console.log(`K-е по счету простое число: ${kthPrime}`);
    } else {
        console.log("Не удалось найти K-е простое число.");
    }
} else {
    console.log("K должно быть целым положительным числом.");
}

PHP

<?php
function isPrime($num) {
    if ($num <= 1) return false;
    if ($num <= 3) return true;
    if ($num % 2 == 0 || $num % 3 == 0) return false;

    for ($i = 5; $i * $i <= $num; $i += 6) {
        if ($num % $i == 0 || $num % ($i + 2) == 0) {
            return false;
        }
    }
    return true;
}

function findKthPrime($k) {
    if ($k == 1) return 2; // Первое простое число
    $count = 1;
    $num = 3; // Начнем с проверки нечетных чисел, так как 2 - первое простое число

    while ($count < $k) {
        if (isPrime($num)) {
            $count++;
        }
        if ($count == $k) {
            return $num;
        }
        $num += 2; // Переходим к следующему нечетному числу
    }
    return -1; // Если не удалось найти K-е простое число
}

if ($_SERVER["REQUEST_METHOD"] == "POST") {
    $k = $_POST["k"];
    if (is_numeric($k) && $k > 0) {
        $kthPrime = findKthPrime(intval($k));
        if ($kthPrime != -1) {
            echo "K-е по счету простое число: $kthPrime";
        } else {
            echo "Не удалось найти K-е простое число.";
        }
    } else {
        echo "K должно быть целым положительным числом.";
    }
}
?>

<!DOCTYPE html>
<html>
<head>
    <title>Поиск K-го простого числа</title>
</head>
<body>
    <form method="post">
        Введите значение K: <input type="text" name="k">
        <input type="submit" value="Найти K-е простое число">
    </form>
</body>
</html>
1 Звезда2 Звезды3 Звезды4 Звезды5 Звезд (Пока оценок нет)
Загрузка...
Давайте поможем друг другу! Если вы нашли ошибку или хотите предложить лучшее решение, пожалуйста, напишите об этом в комментариях.

Может быть полезно

Готовые решения

База данных Access Библиотека

Готовые решения

Программа «Морской бой»

Готовые решения

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

Добавить комментарий

Ваш адрес email не будет опубликован. Обязательные поля помечены *