|
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<long> primeNumbers = new List<long>();
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<long> 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!"
|
|
|
|
|
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
modified 27-May-14 8:40am.
|
|
|
|
|
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 ; )
|
|
|
|
|
In a CAD program, I want to find the (vector) entities that bound a given point.
1) Is a seed fill type algorithm the best choice for this? Or is there a quicker / better / more efficient method?
2) Once I've found my bounding entities, can I make my 'is the boundary contiguous' check fault tolerant to some degree? And what approach would be best? If my line ends aren't coincident, for instance, I could perhaps extended them be a certain tolerance to see if they 'almost cross'? (and then use the 'virtual' vertex in my bonding shape)
Cheers
|
|
|
|
|
A k-d tree ([^]) is good for nearest-neighbor and range searches.
It's like a standard binary search tree, except the discriminant (the value you use to decide on the left or right branches) alternates between the X and Y coordinates at each level.
So at each level, you can eliminate half the search space, depending on if the X or Y coordinates are beyond the point you're searching around. (If neither can be eliminated, you recursively search down both the left and right branches.)
Once you have the entities that are clustered around your point, you can check if they overlap to detect a contiguous entity path around the point.
"Microsoft -- Adding unnecessary complexity to your work since 1987!"
|
|
|
|
|
I have path which is in '*' (asterisk) shape. All the ends are the nodes such that there is 8nodes and one node in the center. I want to form an algorithm that could start the journey from one end and travel to all the other nodes.Can any one guide me through this. How should i proceed the coding?
|
|
|
|
|
There are many ways to do this. Probably the simplest is depth-first search, which visits each unvisited node connected to the current node, recursively.
To implement this, you need a Boolean "visited" member of the node structure, which is initially false in all nodes.
You call the search function with any node to start. The function then sets "visited" to true, and calls itself recursively with each of the node's unvisited neighbors. When it returns at the top level, you've visited all the nodes.
"Microsoft -- Adding unnecessary complexity to your work since 1987!"
|
|
|
|
|
Hello,
Please put a picture of the shape that shows the nodes and paths (lines connecting the nodes) An asterisk has six points, not eight. Maybe you mean a star, then people need to know if you are including the inside corners.
|
|
|
|
|
Dear members,I am trying to do optimization of water supply network by using particle swarm optimization method,and I have the objective function but my problem is how I can use PSO in Matlab,I have tried to download some codes,but still is difficult for me to use it since I am new in optimization,please any help
|
|
|
|
|
I am trying to do problem in which i have numbers of points. Now i need to find the path that goes through all the points. This is not actually TSP because as per my knowledge in TSP it is possible to travel from all points to every other points. But in my case the path network is fixed and i just need to find the path that goes through all the points provided that all points may not have connection to every other point..so what algorithm am i supposed to follow.
|
|
|
|
|
Go ask our friends Google and Wikipedia about "spanning tree". That will get you started, and probably almost finished too.
Cheers,
Peter
Software rusts. Simon Stephenson, ca 1994. So does this signature. me, 2012
|
|
|
|
|
Hello,
So how's it coming along? Do you understand the concept?
With Kind Regards,
April
Comm100 - Leading Live Chat Software Provider
modified 27-May-14 8:35am.
|
|
|
|
|
Hello All.
I own a classified ad site and need several things done to correct and update the code of the site. A nightmare for me, probable only a few days work for you. who ever can do the work will get life time ads space on my site and on my new sites when they go in to production. when completed the newly updated site will be promote world wide , and will have 975 cities listed on it, your ad will be in the computer and code section for the freelancers and it will be listed in all 975 cities! I will consider more than one code warrior for this gig in case the work i need is too much for one person. all involved in the work will get free, life time ad space, which they can sublet if they want and make a profit. interested parties should contact me here. the name of my active site is : Beyslist.com
Thanks Everyone.
|
|
|
|
|
does any one here have any idea of the possibility of creating a classified ad aggregation Algorithm, i am designing a new classified ad service and need in put. we will need such an Algorithm created if we are to move forward, any comments welcome. thanks.
M Bey
|
|
|
|
|
For the very large number like 2^2000 how do I calculate its value?
|
|
|
|
|
Use logarithms.
"Microsoft -- Adding unnecessary complexity to your work since 1987!"
|
|
|
|
|
|
To elaborate on Alan's suggestion...
Let's take a big power of 2, such as:
2 ^ 2000
We first re-express it using a power of 10:
10 ^ (2000 * log10 (2))
Which yields:
10 ^ 602.05999132796239042747778944899
But we want it re-expressed in the more useful form of: man * 10^exp, the scientific notation (just in case).
We know that x^(a+b) == (x^a) * (x^b), where x=10 and (conveniently) a and b can be the integer and the fractional parts of 602.05999132796239042747778944899
In other words:
10 ^ (602 + 0.05999132796239042747778944899) == (10 ^ 602) * (10 ^ 0.05999132796239042747778944899)
We can rearrange it in:
10 ^ 0.05999132796239042747778944899 * 10 ^ 602
Which yields:
1.1481306952742545242328332011881 * 10 ^ 602
And that's the result of 2 ^ 2000:
1.1481306952742545242328332011881e+602
You may calculate this with fixed math, but you won't get as many ULPs and it'll take more time. Either way you're going to get an approximation of the sought value.
The above also works with smaller powers.
A quick demonstration for:
5^3 = 125
Here:
5^3 = 10 ^ (3 * log10 (5))
5^3 = 10 ^ 2.0969100130080564143587833158265
5^3 = 10 ^ (2 + 0.0969100130080564143587833158265)
5^3 = (10 ^ 2) * (10 ^ 0.0969100130080564143587833158265)
5^3 = 10 ^ 0.0969100130080564143587833158265 * 10 ^ 2
5^3 = 1.2499999999999999999999999999985 * 10 ^ 2
5^3 = 1.2499999999999999999999999999985e+2
If we account for the rounding error it becomes familiar:
5^3 = 1.25e+2
5^3 = 125
[edited to improve explanation]
modified 23-Oct-12 6:43am.
|
|
|
|
|
my friend you can use the big integer class it helps you a lot to do such things.
|
|
|
|
|
Use binary:
100000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000b
|
|
|
|
|
More seriously, an easy option is to work in base 1 billion, using an array of integers. Every integer will store 9 significant decimal digits.
It is a rather straightforward matter to implement a doubling algorithm, by means of long addition, as in the following quick Python code.
N= [0] * (Digits - 1) + [1] # Large number representation of 1
for Exponent in range(2000): # Double 2000 times
for Position in range(Digits): # For all digits
N[Position]= 2 * N[Position] # Double this digit
if N[Position] >= Base: # Detect carry out
N[Position]-= Base # Adjust the digit...
N[Position - 1]+= 1 # ... and carry out to the left one
print N
Output:
[0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 114813069, 527425452, 423283320, 117768198, 402231770, 208869520, 47764273, 682576626, 139237031, 385665948, 631650626, 991844596, 463898746, 277344711, 896086305, 533142593, 135616665, 318539129, 989145312, 280000688, 779148240, 44871428, 926990063, 486244781, 615463646, 388363947, 317026040, 466353970, 904996558, 162398808, 944629605, 623311649, 536164221, 970332681, 344168908, 984458505, 602379484, 807914058, 900934776, 500429002, 716706625, 830522008, 132236281, 291761267, 883317206, 598995396, 418127021, 779858404, 42159853, 183251540, 889433902, 91920554, 957783589, 672039160, 81957216, 630582755, 380425583, 726015528, 348786419, 432054508, 915275783, 882625175, 435528800, 822842770, 817965453, 762184851, 149029376]
In reality, this algorithm uses a trick: a carry-in to a digit (from the right) will never cause a carry-out (to the left). This is because the doubled digits are even, at most 999999998, and can stand one incrementation. This allows us to process left-to-right. This property doesn't hold for plain addition where carries can propagate further.
A more efficient but a little more complex solution can be achieved by using a base conversion algorithm.
modified 3-Dec-12 6:44am.
|
|
|
|
|
There is actually a subtle bug in your code. If, on the last pass of your outer loop, one "digit" is == Base - 1 and you carry into it, you never get to carry out of it. If you write your inner loop backwards (or reverse your array), it all comes out in the wash... The point is that multiprecision add/subtract should be done "right to left" so multiplace carry propagation can occur naturally.
A small point, but still important. The one time it bit me, the code was in ROM inside tamper-proof enclosures. A real PITA to fix...
Cheers,
Peter
Software rusts. Simon Stephenson, ca 1994. So does this signature. me, 2012
|
|
|
|
|
You are quite right, sorry for having mislead you.
This is the kind of "off by one" trap I too easily fall into. When I wrote this code I was indeed unsure in what way to go, and I just satisfied myself when I saw successful tests.
There is indeed no carry propagation here and this could have been avoided by careful proofreading: when the carry is made, it applies to digit Position-1, showing that propagation needs to be done by decreasing indexes.
Mea culpa.
How did you discover the flaw ?
|
|
|
|
|
YvesDaoust wrote: How did you discover the flaw ?
In my case, we were doing 32 bit arithmetic on an 8-bit processor. The little machine was attached to the memory system of its larger host, reading messages from there, processing them (cryptographically) and writing the results back. A nasty combination of buffer size and alignment meant that occasionally a block would be read from the wrong place, or, worse, written to the wrong place. Three of us spent a good week staring at code, running simulations and generally not seeing what was under our noses. In the 30-odd years since, I have been sensitised to that kind of bug.
Cheers,
Peter
Software rusts. Simon Stephenson, ca 1994. So does this signature. me, 2012
|
|
|
|
|
General 
News 
Suggestion 
Question 
Bug 
Answer 
Joke 
Praise 
Rant 
Admin 
Submit an article or tip
