|
You have a typo in the definition of the numbers variable. For your code to even compile that would need to be List<Number> numbers = new List<Number>()..., but I can't help but think that this will be very inefficient.
I wasn't, now I am, then I won't be anymore.
|
|
|
|
|
Your code would not even compile, so how can you say it is slow:
List<Number> numbers = new List<Number>() { 2, 3, 4, 5, 6, ... , 2000000 };
for (int i = 0; i < numbers.Count - 1; i++)
if (numbers[i].IsPrime)
for (int j = i + 1; j < numbers.Count - 1; j++)
if (numbers[j].Value % numbers[i].Value == 0)
numbers[j].IsPrime = false;
Regards,
— Manfred
"With sufficient thrust, pigs fly just fine."
Ross Callon, The Twelve Networking Truths, RFC1925
|
|
|
|
|
if you mean this:
List<Number> numbers = new List<Number>() { 2, 3, 4, 5, 6, ... , 2000000 };
it is not the real. I was going to say that I have an array from 2 to 2,000,000.
I just edited the question.
Meysam
|
|
|
|
|
Which part did you edit. The code still is not valid. If you don't use an array or a list of Number instances your algorithm will not compile since you are accessing IsPrime and Value in that loop.
Your code is still broken. 
"With sufficient thrust, pigs fly just fine."
Ross Callon, The Twelve Networking Truths, RFC1925
modified 13-Sep-12 9:12am.
|
|
|
|
|
What are you talking about?
I have tested my code in some low ranges, and it work great.
It Compiles.
Why you say your opinion when you even didn't try it?
Meysam
|
|
|
|
|
If you post code make sure that the code posted will work.
As your question currently stands the code is invalid for the exact reasons I told you.
In your algorithm you are using the properties IsPrime and Value. For that reason the array or list has to contain these kind of objects. Correct the code you posted!
"With sufficient thrust, pigs fly just fine."
Ross Callon, The Twelve Networking Truths, RFC1925
|
|
|
|
|
Meysam Tolouee wrote: It Compiles.
I have just copied the code from your question (as I expect Manfred also did) and it does not compile. Maybe if you copied and pasted the actual code from your program it would make a bit more sense and you would not need to go petulantly down voting Manfred's responses.
One of these days I'm going to think of a really clever signature.
|
|
|
|
|
According to wiki[^]
"The sieve of Eratosthenes is one of the most efficient ways to find all of the smaller primes (below 10 million or so)." (Citation: The Prime Glossary: "The Sieve of Eratosthenes", http://primes.utm.edu/glossary/page.php?sort=SieveOfEratosthenes, references 16. November 2008.)
That should answer your question; The algo is good for the range of numbes you've chosen.
However (and thats a BIG however), your implementation is wrong.
for i = 2, 3, 4, ..., √n :
if A[i] is true:
for j = i2, i2+i, i2+2i, ..., n:
A[j] := false
You've forgotton to only go to the square root of n (Think about why its only necessary to go to sqrt of n!), which takes a HUGE chunk off of the processing. Also, there should be no second if, in that part of the code, you've already multiplied 2 numbers together, so you know the result cannot be prime.
All in all, youve implemented brute force, which is miles slower than the Sieve of Eratosthenesfor finding primes.
|
|
|
|
|
I'm not surprised you find it takes a long time. The time for this algorithm is 0(n log log n). Also, you haven't actually used the Sieve algorithm. What you've done here is a brute force approach. I suggest you read this[^] to see what the algorithm really is.
|
|
|
|
|
Of course I used the algorithm.
If you trace the code you will understand.
Meysam
|
|
|
|
|
No, no you havent. Read my answer for an explanation of why not!
|
|
|
|
|
I wouldn't waste to much time on OP.
I already told OP that he produced invalid code which OP does somehow not understand or chooses to ignore.
I give up! 
Cheers!
"With sufficient thrust, pigs fly just fine."
Ross Callon, The Twelve Networking Truths, RFC1925
|
|
|
|
|
I think actually it's your failing! Its totally understandable what the OP is asking, even if there are some slight misgivings in his code example.
Your comments on this thread are more annoying than his by an order of magnitude.
|
|
|
|
|
I hate to break it to you bubba, but your algorithm isn't that algorithm. You are brute forcing to test against the result of the division to see if the remainder is zero. That's not what this algorithm does; it's a simpler, more elegant implementation. Look at the pseudo code of the wiki page I linked to - that's what your code should look like.
|
|
|
|
|
What have you to say?
I guess you can't collate the code and algorithm, so I help you by this:
List<int> numbers = new List<int>();
for (int i = 2; i < 2000000; i++)
numbers.Add(i);
for (int p = 0; p < numbers.Count - 1; p++)
if (numbers[p].IsPrime)
for (int j = p + 1; j < numbers.Count - 1; j++)
if (numbers[p].IsPrime)
if (numbers[j].Value % numbers[p].Value == 0)
numbers[j].IsPrime = false;
Meysam
modified 12-Sep-12 14:43pm.
|
|
|
|
|
I understood your code perfectly. I can't help it if I'm able to understand algorithms better than you can; it's called age, wisdom and experience.
What I needed you to do is actually go and read the algorithm itself. The sieve is not brute force - your code is. I'm guessing that this is a homework assignment for you, so I'm not going to give you the code - but the pseudocode in the wikipedia article articulates the solution perfectly. Perhaps if you actually tried that algorithm rather then you'd see why I'm saying what it is.
Meysam Tolouee wrote: for (int p = 0; p < numbers.Count - 1; p++)
You don't need to go all the way through to the end of the list. You only need to go to the square root of n.
Meysam Tolouee wrote: if (numbers[j].Value % numbers[p].Value == 0)
Not needed. The sieve doesn't require this test.
|
|
|
|
|
See how point 2 is different from your implementation, and how the description of point 3 is TOTALLY different from your implementation
By way of example I mocked up 2 implementations. The first uses your code:
static void Brute(int max)
{
var numbers = new List<Number>();
for (int i = 2; i < max; i++)
numbers.Add(new Number(i));
var sw = new Stopwatch();
sw.Start();
for (int i = 0; i < numbers.Count - 1; i++)
if (numbers[i].IsPrime)
for (int j = i + 1; j < numbers.Count - 1; j++)
if (numbers[j].Value % numbers[i].Value == 0)
numbers[j].IsPrime = false;
sw.Stop();
Console.WriteLine("Brute: {0}ms",sw.ElapsedMilliseconds);
}
I reduced it to only going to 200000, as it took too long to go all the way to 20000000 for the purpose of this demo:
Result:
Brute: 152009ms
Then I mocked up a very quick Sieve implementation without the enhancements that can be made (described in the wiki article)
-- Code example removed. If this is homework, im not doing it for you.
Result:
Sieve:15ms
The proof, as they say, is in the pudding. In this case Sieve pudding is ready just a little bit quicker
|
|
|
|
|
It is not my homework.
I am solving this.[^]
Also I didn't down vote any of the post in this forum.
Meysam
|
|
|
|
|
Well I can tell you the answer (142913828922 calculated in 386ms), but you should definately try to work out the right algo yourself, its a good learning excercise.
By the way, your original code goes to 20 million, whereas the problem you're solving asks for 2 million.
|
|
|
|
|
It is not important for me to know the answer.
I want to find out the best algorithm, and you are not going to help me.
Thanks anyway.
Meysam
|
|
|
|
|
Meysam Tolouee wrote: nd you are not going to help me.
What the hell do you want him to do ? He has told you in about every possible way how you should improve your code, starting by implementing the algorithm correctly.
~RaGE();
I think words like 'destiny' are a way of trying to find order where none exists. - Christian Graus
Do not feed the troll ! - Common proverb
|
|
|
|
|
We have told you where the algorithm is. You just haven't used it. Seriously, put your preconceptions to one side and take a look at that wiki page. Read the explanation and then carefully read the algorithm presented there. Then try writing it fresh. You'll be amazed at the difference.
|
|
|
|
|
You made a big error in the algorithm as stated above. Also you add work with instantiating classes (struct probably better).
private static bool[] _numbers;
static void Main(string[] args)
{
var sw = new Stopwatch();
sw.Start();
Run();
sw.Stop();
Console.WriteLine("Milliseconds run: " + sw.ElapsedMilliseconds);
Console.WriteLine("Primes: " + _numbers.Count(i => i));
Console.ReadLine();
}
private static void Run()
{
const int count = 2000000;
_numbers = new bool[count];
for (int i = 2; i < count; i++)
_numbers[i] = true;
int baseCounter = 1;
while (baseCounter < count)
{
do
{
baseCounter++;
if (baseCounter == count) return;
} while (!_numbers[baseCounter]);
int counter = baseCounter << 1;
while (counter < count)
{
_numbers[counter] = false;
counter += baseCounter;
}
}
|
|
|
|
|
I want the sum of prime numbers not count of them!
long sum = 0;
for (int i = 0; i < _numbers.Length - 1; i++)
{
if (_numbers[i])
sum += i;
}
Thank you for your time.
Meysam
modified 12-Sep-12 17:12pm.
|
|
|
|
|
If you want the sum or primes then:
static void Main(string[] args)
{
var sw = new Stopwatch();
sw.Start();
Run();
sw.Stop();
Console.WriteLine("Milliseconds run: " + sw.ElapsedMilliseconds);
Console.WriteLine("Primes: " + _numbers.Count(i => i));
var sum = 0;
for (int i = 2; i < _numbers.Count(); i++)
if (_numbers[i]) sum += i;
Console.WriteLine("Sum of Primes: " + sum.ToString("n0"));
Console.ReadLine();
}
|
|
|
|
General 
News 
Suggestion 
Question 
Bug 
Answer 
Joke 
Praise 
Rant 
Admin 
Submit an article or tip
