Автор Валерий Мокрецов задал вопрос в разделе Другие языки и технологии
введено число определить является ли число простым и получил лучший ответ
Ответ от Миоко Таканава[гуру]
1)
module N69492596;
import std.stdio, std.math;
int main(string[] argv)
{
ulong x, b, d = 1;
write("Введите натуральное число: ");
readf("
", &x);
b = cast(ulong)sqrt(x);
while (++d <= b && x % d)
d += !(d < 3);
writef("Число %d ", x);
if (x > 1 && (x < 4 x % d))
writeln("простое");
else
writeln("непростое");
readln();
return 0;
}
2)
module N69492596;
import System.Math as Math;
var x, b, d, s:cardinal;
begin
write("Введите натуральное число: ");
readln(x);
b := cardinal(Math.Sqrt(x));
d := 2;
s := 1;
while (d <= b) & (x mod d # 0) do
inc(d, s);
s := 2
end;
write("Число ", x:4);
if (x > 1) & ((x < 4) or (x mod d # 0)) then
writeln(" простое")
else
writeln(" непростое")
end;
readln
end N69492596.
3)
#include <iostream>
#include <math.h>
using namespace std;
int main()
{
setlocale(LC_ALL,"Russian");
int x;
cout << "Введите натуральное число: ";
cin >> x;
int b = (int)sqrt(x * 1.);
int d = 1;
while (++d <= b && x % d)
d += !(d < 3);
cout << "Число " << x;
if (x > 1 && (x < 4 x % d))
cout << " простое";
else
cout << " непростое";
cin.get();
cin.get();
return 0;
}
На других языках:
Источник:
Простое число - это число, которое имеет только два делителя - 1 и само себя. Кроме единицы. А вообще поиском простых чисел уже очень много лет занимаются много ученых математиков и любителей.
Простые способы нахождения начального списка простых чисел вплоть до некоторого значения дают Решето Эратосфена, решето Сундарама и решето Аткина.
Однако, на практике вместо получения списка простых чисел зачастую требуется проверить, является ли данное число простым. Алгоритмы, решающие эту задачу, называются тестами простоты. Существует множество полиномиальных тестов простоты, но большинство их являются вероятностными (например, тест Миллера — Рабина) и используются для нужд криптографии. В 2002 году было доказано, что задача проверки на простоту в общем виде полиномиально разрешима, но предложенный детерминированный тест Агравала — Каяла — Саксены имеет довольно большую вычислительную сложность, что затрудняет его практическое применение.
Для некоторых классов чисел существуют специализированные эффективные тесты простоты (см. ниже).