[Криптография] Нахождение простого числа

[McLotos]

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

Func Generate()
$n = Random(1000,31357667,1)              ;случайное целое число
$in = $n                                  ;сохраняем его для возврата
If Mod($n, 2) = 0                         ;число должно быть не четным
    Generate()
Else
    For $i = 2 To $i <= $n / $i Step +1
       While Mod($n, $i) = 0
            $n = $n / $i
       WEnd
    Next

     If $n<>$in Then                      ;если получившееся число не равно сгенерированному
	   Generate()
	Else
      Return $in
   EndIf
EndIf
EndFunc

Пока удалось только выяснить что в FOR вообще скрипт не заходит, не могу понять почему

 

[C2H5OH]

В цикл For не заходит потому что результат логической операции False или True (0 или 1), а 2 всегда больше 0 или 1.

По вопросу того что сделал не так.
Встречный вопрос:
Что читал про:
- простые числа,
- программирование,
- рекурсию в программировании
?

 

[McLotos]

В цикл For не заходит потому что результат логической операции False или True (0 или 1), а 2 всегда больше 0 или 1.

Так я же не использую ответ функции для входа в цикл, в цикле четко указано что счетчик $i=2.
И как на него влияет конец функции. Не понимаю.

Что читал про:
- простые числа,
- программирование,
- рекурсию в программировании

Простые числа имеют только 2 делителя - 1 и себя (математика школьный уровень)
Программирование? Ну какбы 4 года колледжа, 3 года академии, 5 лет разработок на php и Delphi. Мноооого всего прочитано, а что?
Рекурсия , точнее рекурсивная функция это функция которая в определенной ситуации вызывает сама себя с новыми входящими параметрами для повторного выполнения.
Кстати в php функция работает, с той лишь разницей что она не сама генерирует число, а получает его извне.

 

[firex]

McLotos
Я не вникал в детали твоего алгоритма, но бросилась в глаза рекурсия. При неблагоприятном стечении обстоятельств твой скрипт вывалится с ошибкой.

 

[McLotos]

McLotos
При неблагоприятном стечении обстоятельств твой скрипт вывалится с ошибкой.

Прикол как раз в том что приложение не выдает никакой ошибки вообще, оно просто закрывается какбудто всё норм


Добавлено:

Сообщение автоматически объединено: 2 Апр 2015

Может кто-нибудь подскажет другой способ генерирования простого числа? =(
Ну или подскажите где у меня тут ошибка, потому-что я совсем уже мозг сломал. В php этот код работает, в autoit не хочет =(

 

[InnI]

McLotos

Не понимаю.

For $i = 2 To $i <= $n / $i Step +1

В AutoIt выражение, стоящее после To (конечное значение), высчитывается один раз в начале цикла и больше не меняется

Спойлер

$a = 2
For $i = 0 To $a
  ConsoleWrite($i & @CRLF)
  $a += 1
Next

У вас результатом данного выражения будет True или False, которое в данном случае будет преобразовано в 1 или 0 соответственно. Начальное значение 2 сразу больше конечного 0/1, поэтому цикл не выполняется.

 

[McLotos]

хмм... дошло =)
Тогда как лучше сделать? Убрать For и вместо него сделать While?

 

[InnI]

McLotos [?]

как лучше сделать

Первую рекурсию можно убрать так

Func Generate()
  Do
    $n = Random(1000,31357667,1) ;случайное целое число
  Until Mod($n, 2)               ;число должно быть нечетным
  $in = $n                       ;сохраняем его для возврата
...

А дальнейшую логику я не понимаю :(

 

[C2H5OH]

Спойлер

$x = Generate()
MsgBox(0,"простое число", $x)

Func Generate()
	Do
		$n = Random(1000,31357667,1)              ;случайное целое число
	Until Prostoe($n)
	Return $n
EndFunc

Func Prostoe($p)
	$maxDiv = Floor(Sqrt($p))
    For $i = 2 To $maxDiv
		If Mod($p, $i) = 0 Then Return False
    Next
	Return True
EndFunc

И при чем тут криптография?...

 

[СН3СН2ОН]

C2H5OH, так и знал что тезка напишет ;D
Вот мой вариан, на удивление тоже самое почти

Спойлер

ConsoleWrite('Сгенерировали простое число ' & Generate() & @CRLF)

Func Generate()
	;Local $min = 1000
	;Local $max = 31357667
	Local $min = 500
	Local $max = 1000
	Local $result = 0
	Local $result_G = 0
	Local $n,$n_1,$n_2 = 0
	$n = Random($min, $max, 1)
	$n_1 = $n
	$n_2 = $n
	;ConsoleWrite($n & @CRLF)
	While 0 = 0
		$result_G = 0
		$n_1 = $n_1 - 1
		$n_2 = $n_2 + 1
		;ConsoleWrite($n_1&@CRLF)
		;ConsoleWrite($n_2&@CRLF)
		If $n_1 = $min Then $n_1 = $n
		If $n_2 = $max Then $n_2 = $n
		$result = $n_1
		For $i = 2 to Ceiling(Sqrt($n_1)) Step 1
			If Mod($n_1,$i) = 0 Then
				;ConsoleWrite('НЕ простое' & @CRLF)
				$result_G += 1
			EndIf
		Next
		If $result_G = 0 Then ExitLoop
		$result = $n_2
		For $i = 2 to Ceiling(Sqrt($n_2)) Step 1
			If Mod($n_2,$i) = 0 Then
				;ConsoleWrite('НЕ простое' & @CRLF)
				$result_G += 1
			EndIf
		Next
		If $result_G = 0 Then ExitLoop
	WEnd

	Return $result
EndFunc   ;==>Generate

Как всегда мой код не оптимален.
А вот функцию Prostoe() by C2H5OH можно ускорить

Спойлер

Func Prostoe($p)
    $maxDiv = Ceiling(Sqrt($p))
	If Mod($p, 2) = 0 Then Return False
    For $i = 3 To $maxDiv Step 2
        If Mod($p, $i) = 0 Then Return False
    Next
    Return True
EndFunc

 

[C2H5OH]

А вот функцию Prostoe() by C2H5OH можно ускорить

Я, когда был студентом, тоже обращал внимание на такие ускорения...
А сейчас они мне не интересны как-то.

 

[McLotos]

И при чем тут криптография?...

Это только одна функция из огромной толпы, предполагаемых функций, и к тому же это будет работать с серверной частью, на которой реализован алгоритм шифрования и дешифрования передачи данных по сессионным ключам клиентских приложений