|
I am performing the Sieve of Eratosthenes algorithm to find prime numbers.
Loading every number from 1 to N into memory makes perfect sense.
Even though this way is slow when calculating larger numbers; its accurate.
This is the only algorithm I know of to tell whether or not a number is prime.
Creating a function IsPrime(long Number) doesn't detect whether a number is prime,
a way of finding out is still needed.
My "prime detection function" is called
sieveofEratosthenes(Int64[] newArray, Int64 newNum)
modified on Sunday, January 31, 2010 3:08 AM
|
|
|
|
|
Well if you have to use it(the sieveofEratosthenes algo) then YES you have to load all numbers.
Else no.
here is a very basic implementation a of prime number finding
private void GetPrimes(long num){
if(num>2) primes.Add(2);
for (long i = 3; i <= num; i++)
{
current=true;
for (long j = 2; j <=num / 2; j++)
{
if ((i % j)==0){
current=false;
break;
}
}
if(current) primes.Add(i);
}
}
Also note that this is a simple brute force algoritm. There are many other a lot faster.
|
|
|
|
|
Your brute finding of prime numbers seems to believe that all the prime numbers up to 50 are as follows:
2 , 29 , 31 , 37 , 41 , 43 , 47
I have thought of many different tricks of finding true prime numbers but to only find that it only works for some.
|
|
|
|
|
Yep my bad. I wrote the "algo" in here. Not in an IDE => mistakes. But it works.
Replace
for (long j = 2; j <= num / 2; j++)
for (long j = 2; j <= i / 2; j++)
|
|
|
|
|
Here is the "algo" written in an IDE and improved. It only checks if it divides by 2 and by the odd numbers.
private void GetPrimes(long num)
{
bool current = true;
for (long i = 2; i <= num; i++)
{
current = true;
if (((i % 2) == 0) && (i != 2))
{
current = false;
}
else
{
for (long j = 3; j <= i / 2; j += 2)
{
if ((i % j) == 0)
{
current = false;
break;
}
}
}
if (current)
{
primes.Add(i);
Console.WriteLine(i.ToString());
}
}
}
|
|
|
|
|
There is no requirement that the numbers are explicitly present, you could use a BitArray where the index is the number (although you might want to use a custom implementation of it, since the one in the .NET framework is slow)
|
|
|
|
|
The index of an array is defined as an int - thus a 32bit signed quantity. So you are definiately limited to a maximum of 2G elements. However, since you are storing int64s in the array, that implies a memory allocation of 16GB - which will almost certainly fail to allocate, certainly in 32bit systems, and probably in 64 bit systems, even with a humungeous swap file.
You are probably going to get better results, faster, by using a deterministic primality test (such as Lucas - see Wiki for details) as it may involve more compuation, but the set-up and storage costs are trivial.
If you must use a sieve, at least create it half the maximum size and treat 1 and 2 as special cases!
All those who believe in psycho kinesis, raise my hand.
My ![Badger | [badger,badger,badger,badger...]](https://www.codeproject.com/script/Forums/Images/badger.gif) 's gonna unleash hell on your ass. tastic!
modified on Sunday, January 31, 2010 10:56 AM
|
|
|
|
|
Thanks, I will definitely check Lucas out.
This is how everything is done so far with my way:
code for button calculate
private void btnCalculate_Click_1(object sender, EventArgs e)<br />
{<br />
listPrimes.Items.Clear();<br />
<br />
String str = txtN.Text.Trim();<br />
Int64 num;<br />
<br />
bool isNum = Int64.TryParse(str, out num);<br />
<br />
if (isNum)<br />
{<br />
sieveofEratosthenes(intCreator(num), num);<br />
}<br />
else<br />
{<br />
MessageBox.Show("Invalid number", "Box for an idiot!");<br />
}<br />
}
code for creating integer array needed for sieve
private Int64[] intCreator(Int64 newNum)<br />
{<br />
try<br />
{<br />
Int64[] numArray = new Int64[newNum +1];<br />
int i = 0;<br />
<br />
foreach (Int64 number in numArray)<br />
{<br />
numArray[i] = i;<br />
i++;<br />
}<br />
<br />
return numArray;<br />
<br />
}<br />
catch(Exception ae)<br />
{<br />
MessageBox.Show(Convert.ToString(ae));<br />
return null;<br />
}<br />
<br />
}
code for prime detection using sieve
private void sieveofEratosthenes(Int64[] newArray, Int64 newNum)<br />
{<br />
Int64 numRoot = Convert.ToInt64(Math.Floor(Math.Sqrt(newNum))); ;<br />
<br />
Boolean[] primeArray = new Boolean[newNum + 1];<br />
<br />
Int64 newInt = 0;<br />
foreach (Boolean flag in primeArray)<br />
{<br />
if (newInt == 0)<br />
{<br />
primeArray[newInt] = false;<br />
newInt++;<br />
}<br />
else if (newInt == 1)<br />
{<br />
primeArray[newInt] = false;<br />
newInt++;<br />
}<br />
else<br />
{<br />
primeArray[newInt] = true;<br />
newInt++;<br />
}<br />
}<br />
<br />
for (int j = 2; j <= numRoot; j++)<br />
{<br />
<br />
if (primeArray[j] == true)<br />
{<br />
Int64 k = j;<br />
<br />
for (Int64 m = 0; m <= newNum; m++)<br />
{<br />
k = k + j;<br />
<br />
if (k <= newNum)<br />
{<br />
primeArray[k] = false;<br />
}<br />
}<br />
}<br />
}<br />
for (Int64 l = 0; l <= newNum; l++)<br />
{ <br />
if (primeArray[l] == true)<br />
{<br />
listPrimes.Items.Add(newArray[l]);<br />
listPrimes.Refresh();<br />
}<br />
}<br />
<br />
}
And that's it. Any ideas or thoughts about my code are greatly appreciated. good or bad.
modified on Sunday, January 31, 2010 4:01 AM
|
|
|
|
|
Why the heck are you allocating an enormous int64 array, when the only place you access it is to get an element out of it - the element value being exactly the same as the index you used to get the element in the first place?
i.e. in all cases newArray[l] == l
It is bad enough that you construct a bool array as well, without allocating a couple of megabytes to hold a number you allready have!
You are aware that a bool is stored as a byte? You might want to consider using a BitArray[^] instead, since that will at least cut your storage by a factor of eight for a very small access overhead.
All those who believe in psycho kinesis, raise my hand.
My 's gonna unleash hell on your ass. tastic!
|
|
|
|
|
Well, the number that's being calculated is input by the user and I used a int64 because i wanted the user to be able to use larger numbers.
I know what you mean about the elements though. I never thought of that.
I original thought I needed a 64 array to hold a large digit number in place.
but if an array has no limits i guess the index would be large itself.
So by using a bitarray I can downsize the memory allocated for the user inputed number?
Awesome.
I also figured there was a way to get rid of the bool array by just displaying the current index of the int array when num was true but that would take entire different approach.
This should help me make better code.
thanks for your responses.
Let me redo my code and post back.
|
|
|
|
|
I agree. I find it sometimes disappointing that indices are int32, not int64, especially for BitArray.
BTW: I happen to have been working on an article with over 20 simple ways to calculate prime numbers op to N while focusing on performance. Right now it finds some 5 million primes per second, and that of course is not using a straight sieve (a waste of memory and cycles), but also nothing as advanced as Lucas tests. I should finish the article...
Luc Pattyn [Forum Guidelines] [Why QA sucks] [My Articles]
I only read code that is properly formatted, adding PRE tags is the easiest way to obtain that. [The QA section does it automatically now, I hope we soon get it on regular forums as well]
|
|
|
|
|
Here is my new and revised Code:
Button Click Event
<br />
private void btnCalculate_Click(object sender, EventArgs e)<br />
{<br />
listPrimes.Items.Clear();<br />
String str = txtN.Text.Trim();<br />
Int64 num;<br />
bool isNum = Int64.TryParse(str, out num);<br />
if (isNum)<br />
{ <br />
Boolean[] boolIndex = new Boolean[num +1];<br />
Int64 newInt = 0;<br />
<br />
foreach (Boolean flag in boolIndex)<br />
{<br />
if (newInt == 0)<br />
{<br />
boolIndex[newInt] = false;<br />
newInt++;<br />
}<br />
else if (newInt == 1)<br />
{<br />
boolIndex[newInt] = false;<br />
newInt++;<br />
}<br />
else<br />
{<br />
boolIndex[newInt] = true;<br />
newInt++;<br />
}<br />
}<br />
<br />
sieveofEratosthenes(boolIndex, num);<br />
}<br />
else<br />
{<br />
MessageBox.Show("Invalid number", "Box for an idiot!");<br />
}<br />
}<br />
The Sieve Prime Detector
<br />
private void sieveofEratosthenes(Boolean[] newBool, Int64 newInt)<br />
{<br />
Int64 numRoot = Convert.ToInt64(Math.Floor(Math.Sqrt(newInt)));<br />
<br />
for (int j = 2; j <= numRoot; j++)<br />
{<br />
<br />
if (newBool[j] == true)<br />
{<br />
Int64 k = j;<br />
<br />
for (Int64 m = 0; m <= newInt; m++)<br />
{<br />
k = k + j;<br />
<br />
if (k <= newInt)<br />
{<br />
newBool[k] = false;<br />
}<br />
}<br />
}<br />
}<br />
for (Int64 l = 0; l <= newInt; l++)<br />
{<br />
if (newBool[l] == true)<br />
{<br />
listPrimes.Items.Add(l);<br />
listPrimes.Refresh();<br />
}<br />
}<br />
<br />
}<br />
Any comments about my code good or bad is greatly appreciated.
modified on Sunday, January 31, 2010 5:39 AM
|
|
|
|
|
A couple of sugestions:
1) You are still using an array of bools => use the BitArray class
2)
Zerodagreez wrote: for (Int64 l = 0; l <= newInt; l++)
{
if (newBool[l] == true)
{
listPrimes.Items.Add(l);
listPrimes.Refresh();
}
}
}
If the number inputed by the user is large the code above will cause a lot of flickering.
use
listPrimes.BeginUpdate()
for (Int64 l = 0; l <= newInt; l++)
{
if (newBool[l] == true)
{
listPrimes.Items.Add(l);
}
}
listPrimes.EndUpdate();
3) Even better than at point 2 you could add it to the list as soon as found.
Put the job/workload in a background worker or separate thread, and from that thread as soon as you find a number that is prime add it to the list
|
|
|
|
|
I tried the bitarray.
It allowed me to set the index to usersNum but would not allow me to set its true or false elements directly as so:
BitArray[] myArray = new bitArray[usersNum];
myArray[0] = false; //error
myArray[1] = false; //error
etc.
Ill check out 3) later. Getting tired.
|
|
|
|
|
Who doesn't 
|
|
|
|
|
Did you actually read up on BitArray at all?
BitArray allNumbers = new BitArray(maxNumber + 1);
for (int i = 0; i < allNumbers.Length; i++)
{
allNumbers.Set(i, true);
}
if (allNumbers[17])
{
MessageBox.Show("Well that one is true!");
}
allNumbers[42] = false;
foreach (bool b in allNumbers)
{
if (!b)
{
MessageBox.Show("But this isn't!");
}
}
All those who believe in psycho kinesis, raise my hand.
My 's gonna unleash hell on your ass. tastic!
|
|
|
|
|
I figured it was just syntax error. 
|
|
|
|
|
An array is indexed by integers regardless of its contained type, so it would be int.MaxValue.
.45 ACP - because shooting twice is just silly
-----
"Why don't you tie a kerosene-soaked rag around your ankles so the ants won't climb up and eat your candy ass..." - Dale Earnhardt, 1997
-----
"The staggering layers of obscenity in your statement make it a work of art on so many levels." - J. Jystad, 2001
|
|
|
|
|
|
But *right now*, int is the same as Int32, so int.MaxValue will return the same as Int32.MaxValue. When/if they change the default integer size in the compiler to 64-bit, int.MaxValue will be the same as Int64.MaxValue.
I was doing this stuff when int was a 16-bit int, and a long was 32-bit. As a matter of fact, I was doing this stuff when an int was 8-bit, and a long was 16-bit.
.45 ACP - because shooting twice is just silly
-----
"Why don't you tie a kerosene-soaked rag around your ankles so the ants won't climb up and eat your candy ass..." - Dale Earnhardt, 1997
-----
"The staggering layers of obscenity in your statement make it a work of art on so many levels." - J. Jystad, 2001
|
|
|
|
|
|
The index of any array is Int32, regardless of what type is stored in the array.
|
|
|
|
|
Maybe he'll understand it better if someone else tells him the same thing I did. LOL!
.45 ACP - because shooting twice is just silly
-----
"Why don't you tie a kerosene-soaked rag around your ankles so the ants won't climb up and eat your candy ass..." - Dale Earnhardt, 1997
-----
"The staggering layers of obscenity in your statement make it a work of art on so many levels." - J. Jystad, 2001
|
|
|
|
|
Yea, sorry about that. I did not notice you actually said "the index of" in your statement. My bad. 
|
|
|
|
|
So, if I understand you correctly the max number of indexes allowed in any array is int.maxvalue?
And not how ever many the cpu can hold up to infinity?
|
|
|
|
General 
News 
Suggestion 
Question 
Bug 
Answer 
Joke 
Praise 
Rant 
Admin 
Submit an article or tip
