Когда мы говорим о простых числах, мы обращаемся к фундаментальному понятию в теории чисел, которое привлекает внимание математиков и компьютерных ученых уже на протяжении многих столетий. Простые числа — это числа, которые имеют всего два делителя: 1 и самих себя. Их уникальные свойства и важность в криптографии, компьютерной науке и многих других областях делают их объектом интенсивного изучения. В этой статье мы рассмотрим одну из самых популярных задач, связанных с простыми числами — программу нахождения всех простых чисел в заданном диапазоне.
Теория
Простое число — число, которое имеет ровно два делителя — единицу и само число. Это означает, что единица не может быть простым числом.
Решето Эратосфена — это эффективный алгоритм для поиска всех простых чисел до заданного натурального числа.
Для примера возьмем диапазон чисел от 1 до 50.
Сначала мы исключаем единицу, так как она не является простым числом.
Затем вы переходите к первому числу, которое не было вычеркнуто, и отмечаете его как простое.
Затем вы вычеркиваете все остальные числа, кратные этому простому числу. Например, 2 — это единственное четное простое число, и мы вычеркиваем все его кратные числа.
Затем переходим к следующему не вычеркнутому числу (3) и делаем то же самое, и так далее.
В результате останутся только простые числа. Например, в диапазоне до 50, мы увидим, что простые числа — это 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43 и 47.
C++
Пример программы на C++, которая находит простые числа в заданном диапазоне. Программа использует метод «Решето Эратосфена» для оптимизации процесса поиска простых чисел.
#include <iostream>
#include <vector>
using namespace std;
// Функция для нахождения всех простых чисел до n
void findPrimes(int n) {
vector<bool> isPrime(n + 1, true);
for (int p = 2; p * p <= n; ++p) {
if (isPrime[p]) {
for (int i = p * p; i <= n; i += p) {
isPrime[i] = false;
}
}
}
cout << "Простые числа в диапазоне от 2 до " << n << ":\n";
for (int i = 2; i <= n; ++i) {
if (isPrime[i]) {
cout << i << " ";
}
}
cout << endl;
}
int main() {
int n;
cout << "Введите верхний предел поиска простых чисел: ";
cin >> n;
if (n >= 2) {
findPrimes(n);
} else {
cout << "Неверный ввод. Пожалуйста, введите число больше или равное 2." << endl;
}
return 0;
}
C#
Пример программы на C#, которая находит простые числа в заданном диапазоне с использованием классического метода проверки каждого числа на простоту.
using System;
class PrimeNumberFinder
{
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;
}
static void FindPrimes(int start, int end)
{
Console.WriteLine($"Простые числа в диапазоне от {start} до {end}:");
for (int i = start; i <= end; i++)
{
if (IsPrime(i))
{
Console.Write(i + " ");
}
}
Console.WriteLine();
}
static void Main()
{
Console.Write("Введите начало диапазона: ");
int start = int.Parse(Console.ReadLine());
Console.Write("Введите конец диапазона: ");
int end = int.Parse(Console.ReadLine());
if (start < 2)
start = 2;
FindPrimes(start, end);
}
}
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_primes(start, end):
print(f"Простые числа в диапазоне от {start} до {end}:")
for num in range(start, end + 1):
if is_prime(num):
print(num, end=" ")
if __name__ == "__main__":
start = int(input("Введите начало диапазона: "))
end = int(input("Введите конец диапазона: "))
if start < 2:
start = 2
find_primes(start, end)
Java
import java.util.Scanner;
public class PrimeNumberFinder {
public 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;
}
public static void findPrimes(int start, int end) {
System.out.println("Простые числа в диапазоне от " + start + " до " + end + ":");
for (int num = start; num <= end; num++) {
if (isPrime(num)) {
System.out.print(num + " ");
}
}
System.out.println();
}
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
System.out.print("Введите начало диапазона: ");
int start = scanner.nextInt();
System.out.print("Введите конец диапазона: ");
int end = scanner.nextInt();
if (start < 2) {
start = 2;
}
findPrimes(start, end);
}
}
Pascal
program PrimeNumberFinder;
var
start, endRange, num, i: Integer;
isPrime: Boolean;
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;
procedure FindPrimes(start, endRange: Integer);
begin
writeln('Простые числа в диапазоне от ', start, ' до ', endRange, ':');
for num := start to endRange do
begin
if IsPrime(num) then
write(num, ' ');
end;
writeln;
end;
begin
write('Введите начало диапазона: ');
readln(start);
write('Введите конец диапазона: ');
readln(endRange);
if start < 2 then
start := 2;
FindPrimes(start, endRange);
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 findPrimes(start, end) {
console.log(`Простые числа в диапазоне от ${start} до ${end}:`);
for (let num = start; num <= end; num++) {
if (isPrime(num)) {
process.stdout.write(num + " ");
}
}
console.log();
}
const readline = require('readline');
const rl = readline.createInterface({
input: process.stdin,
output: process.stdout
});
rl.question('Введите начало диапазона: ', (start) => {
rl.question('Введите конец диапазона: ', (end) => {
start = parseInt(start);
end = parseInt(end);
if (start < 2) {
start = 2;
}
findPrimes(start, end);
rl.close();
});
});
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 findPrimes($start, $end) {
echo "Простые числа в диапазоне от $start до $end:<br>";
for ($num = $start; $num <= $end; $num++) {
if (isPrime($num)) {
echo $num . " ";
}
}
echo "<br>";
}
if ($_SERVER["REQUEST_METHOD"] == "POST") {
$start = (int)$_POST["start"];
$end = (int)$_POST["end"];
if ($start < 2) {
$start = 2;
}
findPrimes($start, $end);
}
?>
<!DOCTYPE html>
<html>
<head>
<title>Нахождение простых чисел</title>
</head>
<body>
<h2>Введите начало и конец диапазона:</h2>
<form method="post" action="<?php echo $_SERVER['PHP_SELF']; ?>">
Начало: <input type="text" name="start"><br>
Конец: <input type="text" name="end"><br>
<input type="submit" value="Найти">
</form>
</body>
</html>
(Пока оценок нет)
Загрузка...