Re: smallest prime number greater than n

On Sep 24, 2:35�pm, "KBH" <K...@xxxxxxxxxxx> wrote:
Computers and programming languages have gotten faster. Trial division (with
purposeful minimum loop overhead) is not a bad way to determine one number
prime or not...up to (say) 18 digits.

It isn't a bad way to test for primality up to say
10^7 or 10^8. But 10^18?? NO WAY.

I suggest that you estimate the time required to prove
primality of an 18-digit number via trial-division.

I can do it in a few 10's of MILLISECONDS with the
proper algorithm. I suggest that you read either
Riesel's book or Crandall & Pomerance's book.


And I'm basing that viewpoint on the
use of Delphi programming language on a 3.2 Pentinum processor.

Coding language is irrelevant. Processor is irrelevant.
You don't want to prove primality via trial division
for anything beyond about 8 digits.

Now trial
division is not a good way to produce a list of prime numbers...and so how
and where to use trial division is a valid subject.

It is a subject that has been well studied and whose
answer is well known. I have told you what it is.


Finally trial division or a multiplication output from wheeled odd numbers
combined with one trial division workload...does not require any advanced
numerical libraries. In other words there are more advanced methods but some
of those methods loose their elegance because of the logistical support that
is required by them.

What have you been smoking??? Trial division on 18 digit
dividends can't be done via even double precision floating
point. It requires multiple-precision arithmetic.

And if you believe that multi-precision arithmetic
routines are 'inelegant' or represent 'advanced math'
then I suggest that you should find another domain of
study. the are the backbone of computational number
theory.

To deny the subject is to be a...book burner.

I'd respond to this, if I could figure out what it means.
Nobody is 'denying' any subject. We are simply telling
you that trial division is the wrong way to do primality
testing.
.

Relevant Pages

  • Re: Q:About primes?
    ... > This prime below with 749 digits required 17+ hours to ... > establish its primality. ... The trick to handling such monsters is to repeatedly divide by ...
    (sci.math)
  • Re: Q:About primes?
    ... >>> processing time to verify its primality than one that ... Your first number is 751 digits. ...
    (sci.math)