Sorry, an error occurred while loading the content.

## Re: [PrimeNumbers] primes in an arithmetic prog.

Expand Messages
• 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
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':
>
>
> 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.