Как узнать, что число делится только на 1 и на себя?

Как узнать, что число делится только на 1 и на себя?
Как узнать, что число делится только на 1 и на себя?
Обрисуйте общий алгоритм нахождения этого числа.
Спасибо)

  • Любое число делится на любое число.
    Ваша задача должна выглядеть как "Определить что натуральное число делится только на 1 или только на себя БЕЗ ОСТАТКА".
    Википедия "Простое число"
    Алгоритмы высшей математики

    Вариант "из простых" -
    Дано натуральное число N
    На каждое натуральное X [2 до N-1] надо взять остаток от деления N на X и сравнить с 0. Если остаток 0, значит число удалось разделить, значит оно делится не только на 1 и N, но и на X
    Для больших чисел это займет огромное количество времени т.к. операция деления самая ресурсоемкая. В добавок вы должны учитывать, что агоритмы деления не идеальны и "бесконечнсть + 1" делить на "бесконечность" на двоичной логике даст не "1.0....01", а "1.0" - можете "попасть"

  • 2 3 5 7 11 13 17 19 23 29 31 37 41 53 59 61 67 71 73 79 83 89 97 101 103 107 109 113 127 131 137 139 149 151 157 163 167 173 179 181 191 193 197 199 211 223 227 229 233 239 241 251 257, а дальше види в поисковой строке гугл список всех простых чисел
  • посмотри в таблицу простых чисел))))))
    Источник: учебник математики 6 класс
  • Наивный алгоритм-1: делим число n на все подряд от 2 до n-1. Если ни на что не поделилось - простое.
    Наивный алгоритм-2: делим число n на все подряд от 2 до n/2. Если ни на что не поделилось - простое (очевидно же, что n не будет делиться ни на что, большее n/2).
    Терпимый алгоритм: делим число n на все подряд от 2 до корня из n. Если не понимаешь, почему - пользуйся предыдущим.
    Рекурсия с кешированием: делим число n на все простые числа от 2 до корня из n. Новое значение простого числа заносим в таблицу.
    Наивный алгоритм-3 (решето Эратосфена) : составляем таблицу из все чисел от 2 до n. Берем первое невычернутое число (2) и вычеркиваем из остальных каждое 2-е (4,6,8...). Берем следующее невычернутое (3) и вычеркиваем каждое 3-е (6,9,12...). ..Берем следующее невычеркнутое (k) и вычеркиваем каждое k-е (2k,3k,4k...) И так - пока не доберемся до n.
  • program prostoe; //простое число
    uses crt;
    var a:boolean;
    i:integer;
    function fl(k: integer): boolean;
    var i:integer;
    begin
    fl:=false;
    for i:=2 to trunc(sqrt(k+1)) do if k mod i = 0 then exit;
    fl:=true;
    end;
    BEGIN
    clrscr;
    write(' ввести целое число -->'); readln(i);
    a:= fl(i) ;
    write(' число ');
    if a then write(i,' простое ') else write(i,' не простое');
    writeln;
    writeln('конец задачи ');
    readkey;
    end.
  • Пробегаем циклом от 3 до корень из N
    проверяем, делится ли число N на числа, заканчивающиеся на 1, 3, 7 и 9, (само число тоже должно заканчиваться на 1, 3, 7 и 9)
    проверка:
    if(N%x == 0)
    {
    ...значит, не наш вариант
    }
    Если число прошло весь цикл, значит, это простое число