2014 dxdy logo

Научный форум dxdy

Математика, Физика, Computer Science, Machine Learning, LaTeX, Механика и Техника, Химия,
Биология и Медицина, Экономика и Финансовая Математика, Гуманитарные науки




Начать новую тему Ответить на тему На страницу Пред.  1, 2
 
 Re: Формула проверки числа на простоту
Сообщение08.03.2017, 20:43 
Заслуженный участник
Аватара пользователя


23/07/05
17989
Москва
Я думаю, что если выкинуть из всех этих формул всякие суммы-произведения, то они станут ещё быстрее и сравняются с пробным делением.

 Профиль  
                  
 
 Re: Формула проверки числа на простоту
Сообщение21.04.2017, 18:52 


22/11/13
155
Someone в сообщении #1198205 писал(а):
Я думаю, что если выкинуть из всех этих формул всякие суммы-произведения, то они станут ещё быстрее и сравняются с пробным делением.

Верно.
Например, число x=123456789123457 - простое, и проверка делением на все нечётные цифры до $\sqrt{x}$ длится 1,5 сек (процессор 16 гегаГерц)

 Профиль  
                  
 
 Re: Формула проверки числа на простоту
Сообщение21.04.2017, 19:00 
Заслуженный участник
Аватара пользователя


06/10/08
6422
ludwig51 в сообщении #1211367 писал(а):
процессор 16 Gb
Простите, что?

 Профиль  
                  
 
 Re: Формула проверки числа на простоту
Сообщение21.04.2017, 19:06 


22/11/13
155
Xaositect в сообщении #1211369 писал(а):
ludwig51 в сообщении #1211367 писал(а):
процессор 16 Gb
Простите, что?

Описка. Исправил.

 Профиль  
                  
 
 Re: Формула проверки числа на простоту
Сообщение21.04.2017, 19:22 
Заслуженный участник
Аватара пользователя


06/10/08
6422
А такого не бывает, если у Вас не сверхсекретные процессоры.
Впрочем, в любом случае 1.5с как-то много, у меня на 4GHz i5 это занимает меньше одной десятой секунды.

 Профиль  
                  
 
 Re: Формула проверки числа на простоту
Сообщение21.04.2017, 20:23 


22/11/13
155
Xaositect в сообщении #1211377 писал(а):
А такого не бывает, если у Вас не сверхсекретные процессоры.
Впрочем, в любом случае 1.5с как-то много, у меня на 4GHz i5 это занимает меньше одной десятой секунды.

У меня программа на визуал Бейсике совместно с Excel, не скомпилированная.
Возможно, если скомпилировать, то будет быстрее.
А текст такой:
Private Sub cmdStart_Click()

Dim x As Double
Dim i As Double
Dim b As Boolean
On Local Error GoTo mExit
x = Range("B3")
Range("C3") = ""

If x / 2 = Int(x / 2) Then
i = 2
If x / 2 > 1 Then
b = True
' No Prime
End If
GoTo m
End If

For i = 3 To Int(Sqr(x)) Step 2
If x / i = Int(x / i) Then
b = True
' No Prime
Exit For
End If
Next i

m:
If b Then
Range("C3") = "No Prime"
Else
Range("C3") = "Prime"
End If
Range("E3") = CStr(i) 'минимальный делитель
Exit Sub
mExit:
MsgBox Error
End Sub

 Профиль  
                  
 
 Re: Формула проверки числа на простоту
Сообщение21.04.2017, 20:25 
Заслуженный участник
Аватара пользователя


23/07/05
17989
Москва

(Оффтоп)

ludwig51 в сообщении #1211367 писал(а):
гегаГерц
Тихий ужас.

 Профиль  
                  
 
 Re: Формула проверки числа на простоту
Сообщение21.04.2017, 22:25 


22/11/13
155
Someone в сообщении #1211399 писал(а):

(Оффтоп)

ludwig51 в сообщении #1211367 писал(а):
гегаГерц
Тихий ужас.

(Оффтоп)

Ошибся в грамматике. Извините.
1 гигагерц=1ГГц=1GHz=$10^9$ Гц=$10^9Hz$

 Профиль  
                  
Показать сообщения за:  Поле сортировки  
Начать новую тему Ответить на тему  [ Сообщений: 23 ]  На страницу Пред.  1, 2

Модераторы: Модераторы Математики, Супермодераторы



Кто сейчас на конференции

Сейчас этот форум просматривают: нет зарегистрированных пользователей


Вы не можете начинать темы
Вы не можете отвечать на сообщения
Вы не можете редактировать свои сообщения
Вы не можете удалять свои сообщения
Вы не можете добавлять вложения

Найти:
Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group