У меня есть новый алгоритм, чтобы найти факторы или простые числа в линейное время - для этого нужна проверка - PullRequest
Новая
       36

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

8 голосов
/ 07 апреля 2011

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

Этот алгоритм находит, является ли заданный номер простым в течение периода времени 5 * N (где N - входное число).Поэтому я надеюсь, что смогу назвать это алгоритмом с линейным временем.

Как я могу проверить, является ли это самым быстрым из доступных алгоритмов?Кто-нибудь может помочь в этом вопросе?(быстрее, чем GNFS и другие известные)

Алгоритм приведен ниже 

Input: A Number (whose factors is to be found)
Output: The two factor of the Number. If the one of the factor found is 1 then it can be concluded that the
Number is prime.

Integer N, mL, mR, r;
Integer temp1; // used for temporary data storage
mR = mL = square root of (N);
/*Check if perfect square*/
temp1 = mL * mR;
if temp1 equals N then
{
  r = 0; //answer is found
  End;
}
mR = N/mL; (have the value of mL less than mR)
r = N%mL;
while r not equals 0 do
{
  mL = mL-1;
  r = r+ mR;

  temp1 = r/mL;
  mR = mR + temp1;
  r = r%mL;
}
End; //mR and mL has answer

Пожалуйста, оставьте свои комментарии. Не стесняйтесь обращаться ко мне за дополнительной информацией.

СпасибоХариш http://randomoneness.blogspot.com/2011/09/algorithm-to-find-factors-or-primes-in.html

Ответы [ 3 ]

14 голосов
/ 07 апреля 2011

«Линейное время» означает время, пропорциональное длине входных данных: в этом случае количество битов в числе, которое вы пытаетесь разложить на множители. Ваш алгоритм не работает за линейное время или что-то близкое к нему, и я боюсь, что он намного медленнее, чем многие существующие алгоритмы факторинга. (Включая, например, GNFS.)

5 голосов
/ 07 апреля 2011

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

2 голосов
/ 07 апреля 2011

Я не присматривался к вашему алгоритму, но тесты простых чисел обычно выполняются быстрее, чем O (n) (где n - входное число).Возьмем, к примеру, этот простой: 

def isprime(n):
   for f in range(2,int(sqrt(n))):
      if n % f == 0:
         return "not prime"
   return "prime"

Здесь он определяется в O (sqrt (n)) , если n простое или нет, просто проверяявсе возможные факторы до sqrt (n) .

...