Re: [PrimeNumbers] primes in an arithmetic prog.
- I already know that the topic doesn't have a lot of
But I hope this can have certain theoretical interest.
This perhaps could help somebody to find an algorithm
--- Phil Carmody <thefatphil@...> escribió: >
--- Sebastian Martin <sebi_sebi@...> wrote:
> > The computational complexity is (nlogn)^3 for thehttp://groups.google.com/groups?th=621fa55443f7d8b3&rnum=1
> > problem 38 formulas, I have not studied the
> > for the problem 39.
> > And the formulas in the article primes in an
> > 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
> 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':
> which was subsequently 'pessimised' in the_______________________________________________________________
> "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
> to whom this has been incorrectly attributed ever
> Do You Yahoo!?
> Yahoo! Finance - Get real-time stock quotes
Nueva versión: Webcam, voz, y mucho más ¡Gratis!
Descárgalo ya desde http://messenger.yahoo.es