Loading ...
Sorry, an error occurred while loading the content.

Re: [PrimeNumbers] primes in an arithmetic prog.

Expand Messages
  • Sebastian Martin
    I already know that the topic doesn t have a lot of practical interest. But I hope this can have certain theoretical interest. This perhaps could help somebody
    Message 1 of 3 , Aug 31, 2002
    • 0 Attachment
      I already know that the topic doesn't have a lot of
      practical interest.

      But I hope this can have certain theoretical interest.

      This perhaps could help somebody to find an algorithm
      but efficient.


      --- Phil Carmody <thefatphil@...> escribió: >
      --- Sebastian Martin <sebi_sebi@...> wrote:
      > > The computational complexity is (nlogn)^3 for the
      > > problem 38 formulas, I have not studied the
      > complexity
      > > for the problem 39.
      > > And the formulas in the article primes in an
      > aritmetic
      > > progression is also polinomial.
      >
      > It depends on how you judge the size of the problem,
      > I should have been more
      > explicit. It's fairly common to view the size of a
      > problem parametrised by
      > the number N as log(N). O(poly(N)) is exponential in
      > log(N).
      >
      > For example, consider the discussions surrounding
      > the recent AKS algorithm.
      > Trial division to sqrt(N) is sub-linear in N, but is
      > expoential in log(N).
      > Trial division would never be described as a
      > sub-linear algorithm in any
      > context I've encountered.
      >
      > Sieving, however, adopts a 'N is linear'
      > nomenclature, as does prime
      > counting, so I did probably chose the wrong default
      > (oh the joys of having
      > two defaults).
      >
      > With that in mind - can you explain why a contrived
      > O(n^(3+eps)) algorithm
      > has any practical merit when there exist
      > O(n^(1+eps)) algorithms or better
      > that do the same job?
      >
      > I am reminded of the classic 'grand revolutionising
      > factoring algorithm':
      >
      >
      http://groups.google.com/groups?th=621fa55443f7d8b3&rnum=1
      > which was subsequently 'pessimised' in the
      > follow-ups.
      >
      >
      > Phil
      >
      >
      >
      > =====
      > "The hottest places in Hell are reserved for those
      > who, in
      > times of moral crisis, preserved their neutrality."
      > -- John F. Kennedy, 24 June 1963, claiming to quote
      > Dante,
      > to whom this has been incorrectly attributed ever
      > since.
      >
      > __________________________________________________
      > Do You Yahoo!?
      > Yahoo! Finance - Get real-time stock quotes
      > http://finance.yahoo.com
      >

      _______________________________________________________________
      Yahoo! Messenger
      Nueva versión: Webcam, voz, y mucho más ¡Gratis!
      Descárgalo ya desde http://messenger.yahoo.es
    Your message has been successfully submitted and would be delivered to recipients shortly.