Си

← →
ferdinando (2007-09-25 13:49) [0]

Как проверить являеться ли число простым на Си?

← →
Jeer © (2007-09-25 13:54) [1]

Также, как и на сотне других императивных языков.
Познакомься поближе с Эратосфеном, он прямо над тобой завис.

← →
Вася Правильный (2007-09-25 14:01) [2]

что такое "простое на Си число"?

← →
Плохиш © (2007-09-25 14:03) [3]

> что такое "простое на Си число"?

это, наверное, такое, которое он смог выговорить и понять :-)

← →
Dib@zol © (2007-09-25 14:07) [4]

А мож тут имеется в виду система единиц СИ, а не язык???

← →
Jeer © (2007-09-25 14:14) [5]

> Вася Правильный (25.09.07 14:01) [2]
>
> что такое "простое на Си число"?

Незабвенный Козьма Прутков говорил, в таких случаях: "Будь прост, но не слишком, простейшее -амеба"
Так пожелаем же всем числам на Си оставаться слегка сложными, э.

← →
БарЛог © (2007-09-25 14:22) [6]

Так выпьем же за кибернетику :)

← →
Игорь Шевченко © (2007-09-25 14:38) [7]

На С все числа простые, сложных там нету.

← →
Washington © (2007-09-25 14:47) [8]

Если ты имеешь ввиду числа, которые делятся только на 1 и на самих себя, то в цикле от 2 до нужного числа-1 дели нужное число на переменную и проверяй результат. Если результат - целое число, то выходи из цикла, твоё нужное число - не простое :), а иначе в общем сам подумай чуток :)

← →
Галинка © (2007-09-25 14:51) [9]

Надо проверять остаток от йелочисленного деления, типа:

enum bool{
false = 0,
true
};

int IsSimole(int val){
if(val % 2 == 0) return false;
return true;
}

усе. Телемаркет.

← →
Галинка © (2007-09-25 14:51) [10]

enum bool{ false = 0, true }; int IsSimрle(int val){ if(!(val % 2)) return false; return true; }

← →
Ega23 © (2007-09-25 14:52) [11]

> Если ты имеешь ввиду числа, которые делятся только на 1
> и на самих себя, то в цикле от 2 до нужного числа-1

Вообще-то до Trunc(sqrt(N))+1

← →
Инс © (2007-09-25 14:54) [12]

В простейшем случае можно воспользоваться перебором, как советуют в [8], только достаточно перебрать числа от двух до корень из твоего, а не твое минус один. В более сложном - см. тест Рабина-Миллера
http://ru.wikipedia.org/wiki/Тест_Миллера_—_Рабина

← →
Washington © (2007-09-25 14:56) [13]

> Инс © (25.09.07 14:54) [12]

Согласен, просто писал так, не раздумывая :)

← →
Галинка © (2007-09-25 14:56) [14]

а не эффективнее проверить просто признаки делимости? Или это сложнее?

← →
Jeer © (2007-09-25 14:56) [15]

> Игорь Шевченко © (25.09.07 14:38) [7]

Числа на Си, также как и на.. наследуют свою карму от Бытия.
Есть хорошие числа (7..), если плохие (13,666..), а есть очень не простые - числа Фибоначчи, Люка, Мерсенна, Ферма.. среди которых загадочным образом появляются и простые.
В общем - есть они:))

← →
Инс © (2007-09-25 14:57) [16]

> а не эффективнее проверить просто признаки делимости?

Ну-ка скажите мне признак делимости на 71? :)

← →
Washington © (2007-09-25 14:59) [17]

Ладно ещё 71, а может скажешь признак делимости на 1873948525? :)))))
Может автору огромные числа проверять надо

← →
Инс © (2007-09-25 15:02) [18]

> Ладно ещё 71, а может скажешь признак делимости на 1873948525?
> :)))))

А это не нужно. То число, что ты привел, делится на 5. Проверять делимость имеет смысл только если делители тоже простые.

← →
Галинка © (2007-09-25 15:04) [19]

Эти огромные могут делиться уже на более маленькие, чем даже 71. Вот и в методе приведенном выше, примерно на этом основываются.

А вот тут обобзенный признак делимости
http://ru.wikipedia.org/wiki/%D0%9F%D1%80%D0%B8%D0%B7%D0%BD%D0%B0%D0%BA_%D0%9F%D0%B0%D1%81%D0%BA%D0%B0%D0%BB%D1%8F

← →
Инс © (2007-09-25 15:06) [20]

> Галинка © (25.09.07 15:04) [19]

А разве не проще поделить и увидеть, делится или нет? Зачем какие-то признаки делимости нужны? Машине ведь не сложно, она поделит, и возмущаться по этому поводу не будет.

← →
Jeer © (2007-09-25 15:08) [21]

А вот так мы ищем "предельно" простые в последовательном массиве 0..N-1:

for i := 2 to High(arSieve) do begin
if arSieve[i] <> 0 then inc(num);
j := i + i;
while j <= High(arSieve) do begin
arSieve[j] := 0;
j := j + i;
end;
end;

← →
Галинка © (2007-09-25 15:09) [22]

Washington © (25.09.07 14:59) [17]

да цикл можно хоть до позеленения вести. Особенно если это тема урока, на котором задали эту задачу. )) Но можно и пофантазировать, как можно ее решить.

Ну зачем, например, пробовать делить на все четные, когда вроде если делится на два, то уже скорее всего делится на 4 или 6 или 8.

← →
Washington © (2007-09-25 15:11) [23]

> Инс © (25.09.07 15:02) [18]

Ну ладно, тогда 1242387421347 :)))

ps наугад набирал

← →
Инс © (2007-09-25 15:11) [24]

> Ну зачем, например, пробовать делить на все четные, когда
> вроде если делится на два, то уже скорее всего делится на
> 4 или 6 или 8.

Наоборот. Если делится на 4, то зачем делить два.

← →
Инс © (2007-09-25 15:13) [25]

> Ну ладно, тогда 1242387421347 :)))

А оно на три делится :)

← →
Инс © (2007-09-25 15:14) [26]

> Ну зачем, например, пробовать делить на все четные, когда
> вроде если делится на два, то уже скорее всего делится на
> 4 или 6 или 8.

Даже правильнее так: если делится на два, то дальше вообще делить не надо :) Число не простое.

← →
Галинка © (2007-09-25 15:15) [27]

Да просто скорее всего, если число составное, то цикл кончится уже в числах до 20.

Washington © (25.09.07 15:11) [23]

оно не простое. Оно на три делится точно. По признаку делимости )) Сумма его цифр = 48.

← →
Washington © (2007-09-25 15:16) [28]

Фтопку. Говорю же наугад писАл. :) НО я уверен что можно найти большо-о-о-ое простое число. И поди-ка ты проверь все признаки делимости для него.

← →
Инс © (2007-09-25 15:17) [29]

> Да просто скорее всего, если число составное, то цикл кончится
> уже в числах до 20.

Бывают и более сложные задачи. Например в криптоалгоритме RSA для генерации ключевой пары необходимо выбрать простые числа порядка 512 бит длины. Вот тут проверить так не получится. Только тест Миллера-Рабина.

> Галинка © (25.09.07 15:15) [27]

А я не помню, делится ли 48 на три или нет.

А вот Сумма/Сумма/Сумма.. его цифр - 3, значит делится:)

> А я не помню, делится ли 48 на три или нет.

жестоко...

Jeer © (25.09.07 15:18) [30]

ну можно и так. Но я числа до ста вполне держу в голове. Точнее они сами там как-то держатся. Таблицей умножения наверное.

для маленьких чисел - решето Эратосфена.

> Галинка © (25.09.07 15:21) [32]

Если в голове много свободного места - рекомендую:

http://primes.utm.edu/primes/lists/all.txt

> Галинка © (25.09.07 15:15) [27]
> Да просто скорее всего, если число составное, то цикл кончится
> уже в числах до 20.

А как же 529?

Denis_ © (25.09.07 15:22) [33]
Для маленьких чисел, миллионов где-нибудь до 10, можно завести таблицу.
И искать бинарным поиском.

Как демонстрируют практики, простые числа с миллионами значащих цифр находятся с помощью совсем уж не Cray-system:
M32582657 9,808,358 2006 Pentium 4 (3 GHz)

> Jeer (25.09.2007 15:18:30) [30]

Продолжать дальше складывать, пока не останется число из одно цифры 3/6/9

> Anatoly Podgoretsky © (25.09.07 15:43) [39]

Во ! Я ж говорю, нас одни мэтры учили, а чему не доучились - сами придумаем и скажем, что так оно и было.

> Сумма/Сумма/Сумма.

Алгоритм, однако:))

Чего думать, трясти надо - решето

Си Найти похожие ветки