Re: Prime Candidates

From: Dan (30pack_at_sbcglobal.net)
Date: 06/23/04 

Date: Wed, 23 Jun 2004 01:28:41 +0000 (UTC)

On 22 Jun 2004, vernonner3voltazim wrote:
>When generating a series of numbers to test for primality,
>it would be nice to have a way to avoid generation of as
>many numbers as possible that cannot possibly be prime.
>I have proposed a simple algorithm here:
>http://www.halfbakery.com/idea/Prime_20Candidates#1087930489
>I will not be in the least surprised it this is widely
>known among number theorists. But maybe it isn't.
>(Or, maybe it has been discovered multiple times, and
>immediately sneered and ignored and never published.
>I wouldn't be surprised at that, either!)
>
>Let me know, please!
>Thanks in advance!

It seems like you are making this process all to difficult.

I did a simple basic program that uses the method below in
an algorithm to find all primes in a given range (n) from prime
7--->n.

Just add and keep repeating this sequence ---->oo

7+
  4+2+4+2+4+6+2+6
 +4+2+4+2+4+6+2+6
 +4+2+4+2+4+6+2+6
 +4.. etc.

At any point of these summations of integers, they are either prime
or have prime factors =>7.

So for finding primes in a range of integers from 7 ---> n it uses
about 26.66..% of all integers in that range.
The least integers needed in that range to test for their primality!
The larger the n the more (6)s will be added to this decimal
expansion of the percentage.
There are much more sophisticated and faster ways to find primes but
this is the easiest sieve to construct which automatically
eliminates all even integers and all 0(mod 3) and 0(mod 5) that are
composites >7.
Primes 2,3 and 5 are not included in this footprint. Prime 7 is used
to start the initial summing process.

Dan

Relevant Pages

  • Re: EFFICIENCY: PRIME TEST vs PRIME GENERATOR
    ... > Let's suppose we have an algorithm that will take a positive ... > For example, the USUAL test runs on odd numbers, checking for primality. ... > The time it takes to prove one such number is either composite or prime is ... > you DON'T use every partition, you might require very large exponents. ...
    (sci.math)
  • Diminished Radix parameters for DSA
    ... Algorithm Standard parameters the other day. ... bother checking p or q for primality. ... Greg Rose ...
    (sci.crypt)
  • Re: Prime Candidates
    ... 30pack@sbcglobal.net (Dan) wrote: ... >>it would be nice to have a way to avoid generation of as ... preventing Candidates from being divisible by any prime < 17: ... which should then be tested for Primality. ...
    (sci.math)
  • Re: PKI: the end
    ... the published deterministic polynomial algorithm ... The usual primality test is Rabin-Miller, with a fixed failure ... number is prime with probability at least 1-2^. ...
    (sci.crypt)
  • Re: primality
    ... no it isn't because a random prime only needs to be tested for primality ... a twin prime has to test for primality of both numbers as not all ... a third random number is generated and ... i'll use the one out of my algorithm. ...
    (sci.crypt)