Prime Number Generation
-
I first noticed this when I was in high school. But I can't seem to find any references to it on the Internet, did I discover something previously unknown? I'm sure the algorithm can be made more efficient using other rules for generating prime numbers, but I'm just curious if anyone has even seen this before, and who (if not me), first discovered this. How I'm generate prime numbers... 1. 2 is not include 2. Insert 3 and 5 into the prime number set 3. The next prime number is 7 = 5 + 3 - 1 4. The next prime number is 11 = 7 + 5 - 1 5. The next prime number is 13 = 11 + 3 - 1 So (Next Prime) = (Last Prime) + (Some Smaller Prime) - 1 Here is some C# code, showing this...
void Test()
{
List primeNumbers = new List();
primeNumbers.Add(3);
primeNumbers.Add(5);
DateTime stopTime = DateTime.Now + new TimeSpan(0, 10, 0);
Console.Write("Calculating prime numbers...");
while (DateTime.Now < stopTime)
{
if (primeNumbers.Count % 100 == 0)
Console.Write(".");
primeNumbers.Add(GetNextPrime(primeNumbers));
}
Console.WriteLine("Calculated " + primeNumbers.Count + " prime numbers.");
Console.WriteLine("The largest being " + primeNumbers.Last() + ".");
}long GetNextPrime(List primeNumbers)
{
long lastPrime = primeNumbers.Last();
for (int i = 0; i < primeNumbers.Count - 1; i++)
{
long testValue = lastPrime + primeNumbers[i] - 1;
bool fail = false;
for (int j = 0; j < primeNumbers.Count - 1; j++)
{
if (testValue % primeNumbers[j] == 0)
{
fail = true;
break;
}
}
if (fail) continue;
return testValue;
}
throw new Exception("Rule failed");
} -
I first noticed this when I was in high school. But I can't seem to find any references to it on the Internet, did I discover something previously unknown? I'm sure the algorithm can be made more efficient using other rules for generating prime numbers, but I'm just curious if anyone has even seen this before, and who (if not me), first discovered this. How I'm generate prime numbers... 1. 2 is not include 2. Insert 3 and 5 into the prime number set 3. The next prime number is 7 = 5 + 3 - 1 4. The next prime number is 11 = 7 + 5 - 1 5. The next prime number is 13 = 11 + 3 - 1 So (Next Prime) = (Last Prime) + (Some Smaller Prime) - 1 Here is some C# code, showing this...
void Test()
{
List primeNumbers = new List();
primeNumbers.Add(3);
primeNumbers.Add(5);
DateTime stopTime = DateTime.Now + new TimeSpan(0, 10, 0);
Console.Write("Calculating prime numbers...");
while (DateTime.Now < stopTime)
{
if (primeNumbers.Count % 100 == 0)
Console.Write(".");
primeNumbers.Add(GetNextPrime(primeNumbers));
}
Console.WriteLine("Calculated " + primeNumbers.Count + " prime numbers.");
Console.WriteLine("The largest being " + primeNumbers.Last() + ".");
}long GetNextPrime(List primeNumbers)
{
long lastPrime = primeNumbers.Last();
for (int i = 0; i < primeNumbers.Count - 1; i++)
{
long testValue = lastPrime + primeNumbers[i] - 1;
bool fail = false;
for (int j = 0; j < primeNumbers.Count - 1; j++)
{
if (testValue % primeNumbers[j] == 0)
{
fail = true;
break;
}
}
if (fail) continue;
return testValue;
}
throw new Exception("Rule failed");
}There is no simple algorithm for generating prime numbers. For example, your method falls apart when you take the next step: 11 + 5 - 1 = 15, which isn't prime. A foolproof (but slower) method is to try dividing a candidate by all the integers up to the square root of that number. If none can divide it evenly, it's prime. Also look at: http://en.wikipedia.org/wiki/Sieve_of_Eratosthenes[^]
"Microsoft -- Adding unnecessary complexity to your work since 1987!"
-
I first noticed this when I was in high school. But I can't seem to find any references to it on the Internet, did I discover something previously unknown? I'm sure the algorithm can be made more efficient using other rules for generating prime numbers, but I'm just curious if anyone has even seen this before, and who (if not me), first discovered this. How I'm generate prime numbers... 1. 2 is not include 2. Insert 3 and 5 into the prime number set 3. The next prime number is 7 = 5 + 3 - 1 4. The next prime number is 11 = 7 + 5 - 1 5. The next prime number is 13 = 11 + 3 - 1 So (Next Prime) = (Last Prime) + (Some Smaller Prime) - 1 Here is some C# code, showing this...
void Test()
{
List primeNumbers = new List();
primeNumbers.Add(3);
primeNumbers.Add(5);
DateTime stopTime = DateTime.Now + new TimeSpan(0, 10, 0);
Console.Write("Calculating prime numbers...");
while (DateTime.Now < stopTime)
{
if (primeNumbers.Count % 100 == 0)
Console.Write(".");
primeNumbers.Add(GetNextPrime(primeNumbers));
}
Console.WriteLine("Calculated " + primeNumbers.Count + " prime numbers.");
Console.WriteLine("The largest being " + primeNumbers.Last() + ".");
}long GetNextPrime(List primeNumbers)
{
long lastPrime = primeNumbers.Last();
for (int i = 0; i < primeNumbers.Count - 1; i++)
{
long testValue = lastPrime + primeNumbers[i] - 1;
bool fail = false;
for (int j = 0; j < primeNumbers.Count - 1; j++)
{
if (testValue % primeNumbers[j] == 0)
{
fail = true;
break;
}
}
if (fail) continue;
return testValue;
}
throw new Exception("Rule failed");
}Hello there, Prime Number Generating Algorithm: A Prime Sieve or Prime Number Sieve is defined to be a fast type of algorithm for finding prime numbers. There are quite a lot of prime sieves that can be found. So the question remains: which one should I implement? First we must ask: exactly how does a Prime Sieve work? What does it do? Well, here's the answer! A prime sieve works by creating a list of all integers up to a what ever limit and then progressively removing numbers that are made up of multiple elements (composite)until only primes numbers remain. This is one of the most known the most efficient ways to obtain a large range of prime numbers. Live Support Software for Busines
April Comm100 - Leading Live Chat Software Provider
-
I first noticed this when I was in high school. But I can't seem to find any references to it on the Internet, did I discover something previously unknown? I'm sure the algorithm can be made more efficient using other rules for generating prime numbers, but I'm just curious if anyone has even seen this before, and who (if not me), first discovered this. How I'm generate prime numbers... 1. 2 is not include 2. Insert 3 and 5 into the prime number set 3. The next prime number is 7 = 5 + 3 - 1 4. The next prime number is 11 = 7 + 5 - 1 5. The next prime number is 13 = 11 + 3 - 1 So (Next Prime) = (Last Prime) + (Some Smaller Prime) - 1 Here is some C# code, showing this...
void Test()
{
List primeNumbers = new List();
primeNumbers.Add(3);
primeNumbers.Add(5);
DateTime stopTime = DateTime.Now + new TimeSpan(0, 10, 0);
Console.Write("Calculating prime numbers...");
while (DateTime.Now < stopTime)
{
if (primeNumbers.Count % 100 == 0)
Console.Write(".");
primeNumbers.Add(GetNextPrime(primeNumbers));
}
Console.WriteLine("Calculated " + primeNumbers.Count + " prime numbers.");
Console.WriteLine("The largest being " + primeNumbers.Last() + ".");
}long GetNextPrime(List primeNumbers)
{
long lastPrime = primeNumbers.Last();
for (int i = 0; i < primeNumbers.Count - 1; i++)
{
long testValue = lastPrime + primeNumbers[i] - 1;
bool fail = false;
for (int j = 0; j < primeNumbers.Count - 1; j++)
{
if (testValue % primeNumbers[j] == 0)
{
fail = true;
break;
}
}
if (fail) continue;
return testValue;
}
throw new Exception("Rule failed");
}Hi The catch with prime numbers is that to this day there's no algorithm that will find them all in any given interval without resorting to any form of trial and error or anyway without making any comparison against a set of pregress data. Unbelievable as it sounds, that's the current truth. Should you discover such an algorithm it'd earn you both a Nobel and a very fat place in hystory, hands down. Keep trying and keep hoping ; )