Почему цикл работает пока i*i< введенного числа?

@MrRovax · Регистрация: 03.09.2015

Author24 — интернет-сервис помощи студентам

Проверка на простое или составное число.

C

int Prime ( int N ) 
{
for ( int i = 2; i*i <= N; i ++ ) 
if ( N % i == 0 ) return 0; 
return 1;

Добавлено через 38 секунд
Почему именно возводится в квадрат?

@Fonduee · 03.09.2015, 22:13

Сообщение от MrRovax

Почему именно возводится в квадрат?

Потому, что i * (i - 1), i * (i - 2), ..., i * (i - (i - 1)) не могут быть простыми, ибо кроме 1, у них как минимум есть еще один делитель, сам i.

@MrRovax · 03.09.2015, 22:43 **[ТС]**

Вы меня простите я на 1 курсе, но откуда вообще взялся i*(i-1)? Как это относится к делителям 1 и самому i?

Добавлено через 4 минуты
В цикле есть проверка на делитель, но почему он робит до i*i?

Добавлено через 20 секунд
Пример из Полякова

Добавлено через 2 минуты
i*i тут сам делитель находится вот оно что

@Даценд · 03.09.2015, 22:49

Если рассмотреть следующую таблицу, то можно увидеть, что делить на числа, квадрат которых большие N смысла нет, так как результатом деления будут числа, на которые число N уже делилось.

@MrRovax · 03.09.2015, 22:58 **[ТС]**

Даценд, я бы тебе подарил пирожок, теперь стало ЯСНО, но как заранее мне как программисту мне узнать что в цикле нужен i*i? К примеру на сессии?

Добавлено через 4 минуты
Даценд, Я понял, мне нужно додуматься своей бошкой, что дальше если мы делим то рез-ты будут меньше и соответственно мы используем цикл for. Всем спасибо)

Байт · 03.09.2015, 22:58

Пусть N делится на k и k*k > N. Тогда N делится на i = N/k, но i*i < N, то есть этот случай мы уже в цикле

C

1	for(i=2; i*i<=N; i++)

рассмотрели.

Сообщение от Fonduee

Потому, что i * (i - 1), i * (i - 2), ..., i * (i - (i - 1)) не могут быть простыми, ибо кроме 1, у них как минимум есть еще один делитель, сам i.

Простите, ничего не понял. А вы?

@Даценд · 03.09.2015, 23:11

Сообщение от MrRovax

Я понял, мне нужно додуматься своей бошкой

Не обязательно. Думаю, будет предмет типа Теории алгоритмов, где в том числе расскажут и об алгоритмах поиска простых чисел.

@MrRovax · 03.09.2015, 23:15 **[ТС]**

Байт, Вы отлично расписали формулу по которой работает цикл.

Добавлено через 58 секунд
Даценд, верно, алгоритмы будут в программе по вышке.

@Fonduee · 03.09.2015, 23:18

Сообщение от MrRovax

К примеру на сессии?

Область дискретной математики, если проходили - будете знать, если нет, то пройдёте. На сессии не спрашивают, то чего еще не было, или не интердисциплинарно.

Сообщение от Байт

Простите, ничего не понял. А вы?

Мы то поняли,

почти та же кобыла, только вид с другой стороны.

Байт · 04.09.2015, 09:08

Сообщение от Fonduee

Мы то поняли, почти та же кобыла, только вид с другой стороны.

Туповат стал чего-то.То, что числа i*(i-1), ... i*(i-2) - составные, с этим я не спорю. Кстати, последнее ваше число i*(i-(i-1)) = i*1 = i - не обязательно составное.
Но как из этого соображения следует, что делители большие sqrt(N) рассматривать не стоит - это для меня загадка

@Fonduee · 04.09.2015, 10:12

Сообщение от Байт

рассматривать не стоит - это для меня загадка

Вывод более интуитивный, нежели научный. Суть состояла в том, что мы имеем последовательность

$https://www.cyberforum.ru/cgi-bin/latex.cgi? i \ast (i - (i - 2)), \: i \ast (i - (i - 3)), \: ..., \: i \ast (i - 2), \: i \ast (i - 1), \: i \ast i, \: i \ast (i + 1), \: i \ast (i + 2), \: ...$

То, что продукты чисел

$https://www.cyberforum.ru/cgi-bin/latex.cgi?(i - k)\: \mid \: k \: \in \: \begin{Bmatrix} 2,\: ...,\: i - 1) \end{Bmatrix}$

не являются простыми (Хотя сами числа могум ими быть, но они меньше N, а значит нам не интересны), мы знаем из предыдущих итераций, а вот о числах больше i, мы ничего не знаем. Хоть и логично, что продукты

$https://www.cyberforum.ru/cgi-bin/latex.cgi?..., i \ast (i + 1), \: i \ast (i + 2), \: ...$

не простые. О самих же

$https://www.cyberforum.ru/cgi-bin/latex.cgi?(i + k) \: \mid \: k \: \in \: \begin{Bmatrix} 1, \: ... \end{Bmatrix}$

мы мало что можем сказать, ибо мы их проверим только в "будущем". Отсюда следует, что максимум мы можем быть уверены, в числах только до i * i, но не более.

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

Байт · 04.09.2015, 10:24

Сообщение от Fonduee

Вывод более интуитивный, нежели научный.

Ну, если интуитивный...

Да, не такой уж я и тупой, что-то начал понимать... Но сложновато как-то... Такая простенькая задачка, а тут продукты, последовательности, надежды на будущее...
Впрочем, давно замечено, что работы первооткрывателей часто неуклюжи...

@Fonduee Музыка нас Связала 232 / 232 / 52 Регистрация: 26.03.2008 Сообщений: 616
	03.09.2015, 22:13	2
	Сообщение от MrRovax Почему именно возводится в квадрат? Потому, что i * (i - 1), i * (i - 2), ..., i * (i - (i - 1)) не могут быть простыми, ибо кроме 1, у них как минимум есть еще один делитель, сам i. 1

@MrRovax 0 / 0 / 0 Регистрация: 03.09.2015 Сообщений: 10
	03.09.2015, 22:43 [ТС]	3
	Вы меня простите я на 1 курсе, но откуда вообще взялся i(i-1)? Как это относится к делителям 1 и самому i? Добавлено через 4 минуты* В цикле есть проверка на делитель, но почему он робит до ii? Добавлено через 20 секунд* Пример из Полякова Добавлено через 2 минуты i*i тут сам делитель находится вот оно что 0

@Даценд 5871 / 4748 / 2940 Регистрация: 20.04.2015 Сообщений: 8,361
	03.09.2015, 22:49	4
	Если рассмотреть следующую таблицу, то можно увидеть, что делить на числа, квадрат которых большие N смысла нет, так как результатом деления будут числа, на которые число N уже делилось. Миниатюры 1

@MrRovax 0 / 0 / 0 Регистрация: 03.09.2015 Сообщений: 10
	03.09.2015, 22:58 [ТС]	5
	Даценд, я бы тебе подарил пирожок, теперь стало ЯСНО, но как заранее мне как программисту мне узнать что в цикле нужен ii? К примеру на сессии? Добавлено через 4 минуты* Даценд, Я понял, мне нужно додуматься своей бошкой, что дальше если мы делим то рез-ты будут меньше и соответственно мы используем цикл for. Всем спасибо) 0

@Даценд 5871 / 4748 / 2940 Регистрация: 20.04.2015 Сообщений: 8,361
	03.09.2015, 23:11	7
	Сообщение от MrRovax Я понял, мне нужно додуматься своей бошкой Не обязательно. Думаю, будет предмет типа Теории алгоритмов, где в том числе расскажут и об алгоритмах поиска простых чисел. 0

@MrRovax 0 / 0 / 0 Регистрация: 03.09.2015 Сообщений: 10
	03.09.2015, 23:15 [ТС]	8
	Байт, Вы отлично расписали формулу по которой работает цикл. Добавлено через 58 секунд Даценд, верно, алгоритмы будут в программе по вышке. 0

@Fonduee Музыка нас Связала 232 / 232 / 52 Регистрация: 26.03.2008 Сообщений: 616
	03.09.2015, 23:18	9
	Сообщение от MrRovax К примеру на сессии? Область дискретной математики, если проходили - будете знать, если нет, то пройдёте. На сессии не спрашивают, то чего еще не было, или не интердисциплинарно. Сообщение от Байт Простите, ничего не понял. А вы? Мы то поняли, почти та же кобыла, только вид с другой стороны. 0

Байт Диссидент 27706 / 17322 / 3812 Регистрация: 24.12.2010 Сообщений: 38,979
	04.09.2015, 09:08	10
	Сообщение от Fonduee Мы то поняли, почти та же кобыла, только вид с другой стороны. Туповат стал чего-то.То, что числа i(i-1), ... i(i-2) - составные, с этим я не спорю. Кстати, последнее ваше число i(i-(i-1)) = i1 = i - не обязательно составное. Но как из этого соображения следует, что делители большие sqrt(N) рассматривать не стоит - это для меня загадка 0

@Fonduee Музыка нас Связала 232 / 232 / 52 Регистрация: 26.03.2008 Сообщений: 616
	04.09.2015, 10:12	11
	Сообщение от Байт рассматривать не стоит - это для меня загадка Вывод более интуитивный, нежели научный. Суть состояла в том, что мы имеем последовательность $https://www.cyberforum.ru/cgi-bin/latex.cgi? i \ast (i - (i - 2)), \: i \ast (i - (i - 3)), \: ..., \: i \ast (i - 2), \: i \ast (i - 1), \: i \ast i, \: i \ast (i + 1), \: i \ast (i + 2), \: ...$ То, что продукты чисел $https://www.cyberforum.ru/cgi-bin/latex.cgi?(i - k)\: \mid \: k \: \in \: \begin{Bmatrix} 2,\: ...,\: i - 1) \end{Bmatrix}$ не являются простыми (Хотя сами числа могум ими быть, но они меньше N, а значит нам не интересны), мы знаем из предыдущих итераций, а вот о числах больше i, мы ничего не знаем. Хоть и логично, что продукты $https://www.cyberforum.ru/cgi-bin/latex.cgi?..., i \ast (i + 1), \: i \ast (i + 2), \: ...$ не простые. О самих же $https://www.cyberforum.ru/cgi-bin/latex.cgi?(i + k) \: \mid \: k \: \in \: \begin{Bmatrix} 1, \: ... \end{Bmatrix}$ мы мало что можем сказать, ибо мы их проверим только в "будущем". Отсюда следует, что максимум мы можем быть уверены, в числах только до *i i**, но не более. Ваш вариант был более коротким, и с формулой, для лучшего пониманая, но суть та же, максимальный лимит на проверку. 0

Байт Диссидент 27706 / 17322 / 3812 Регистрация: 24.12.2010 Сообщений: 38,979
	04.09.2015, 10:24	12
	Сообщение от Fonduee Вывод более интуитивный, нежели научный. Ну, если интуитивный... Да, не такой уж я и тупой, что-то начал понимать... Но сложновато как-то... Такая простенькая задачка, а тут продукты, последовательности, надежды на будущее... Впрочем, давно замечено, что работы первооткрывателей часто неуклюжи... 0

Почему цикл работает пока i*i< введенного числа?

Решение