CodeGuru Home VC++ / MFC / C++ .NET / C# Visual Basic VB Forums Developer.com
Page 1 of 3 123 LastLast
Results 1 to 15 of 39

Thread: Prime Numbers

  1. #1
    Join Date
    May 2004
    Posts
    249

    Question Prime Numbers

    I wouldn't be suprised if this question had been posted earlier. But i would like to streamline it a little bit so that i get to know what i m trying to find out......

    So if i write a Loop to calculate Prime Numbers in order, is there any way possible for this to happen in a shorter period of time.

    the loop that i constructed took about 11hrs on a Win 7 2GB ram machine to calculate about 150,000 primes, could this be done any faster................


    Thanks again for any inputs whatsoever.

  2. #2
    Join Date
    Jan 2006
    Location
    Singapore
    Posts
    6,765

    Re: Prime Numbers

    Use a better or more appropriate algorithm, e.g., the sieve of Eratosthenes may be applicable.
    C + C++ Compiler: MinGW port of GCC
    Build + Version Control System: SCons + Bazaar

    Look up a C/C++ Reference and learn How To Ask Questions The Smart Way
    Kindly rate my posts if you found them useful

  3. #3
    Join Date
    Jul 2005
    Location
    Netherlands
    Posts
    2,042

    Re: Prime Numbers

    Quote Originally Posted by rockx View Post
    So if i write a Loop to calculate Prime Numbers in order, is there any way possible for this to happen in a shorter period of time.

    the loop that i constructed took about 11hrs on a Win 7 2GB ram machine to calculate about 150,000 primes, could this be done any faster................
    Please show us your code.
    Did you run a fully optimized build of your program?
    Cheers, D Drmmr

    Please put [code][/code] tags around your code to preserve indentation and make it more readable.

    As long as man ascribes to himself what is merely a posibility, he will not work for the attainment of it. - P. D. Ouspensky

  4. #4
    2kaud's Avatar
    2kaud is offline Super Moderator Power Poster
    Join Date
    Dec 2012
    Location
    England
    Posts
    7,822

    Re: Prime Numbers

    Oh wow! I just tried my prime number generator and it took 672 milliseconds to calculate the first 150,000 prime numbers (39,625 milliseconds to calculate and display them in a console window). I'm using Windows XP 2.37GHz 2Mb memory.

    I think you have a problem with your algorithm. As D_Drmmr said in post #3, if you post your code we'll provide guidance.
    All advice is offered in good faith only. All my code is tested (unless stated explicitly otherwise) with the latest version of Microsoft Visual Studio (using the supported features of the latest standard) and is offered as examples only - not as production quality. I cannot offer advice regarding any other c/c++ compiler/IDE or incompatibilities with VS. You are ultimately responsible for the effects of your programs and the integrity of the machines they run on. Anything I post, code snippets, advice, etc is licensed as Public Domain https://creativecommons.org/publicdomain/zero/1.0/ and can be used without reference or acknowledgement. Also note that I only provide advice and guidance via the forums - and not via private messages!

    C++23 Compiler: Microsoft VS2022 (17.6.5)

  5. #5
    Join Date
    May 2004
    Posts
    249

    Re: Prime Numbers

    Here is my Code..........Please Help!!!

    Code:
    #include <iostream.h>
    #include <fstream.h>
    #include <string.h>
    #include <conio.h>
    #include <stdlib.h>
    
    void main()
    {
    	long int i=0,c=1,n,j;
    	ofstream myfile ("Prime.doc");
    	if (myfile.is_open())
    {
    	while (c <= 150000)
    	{
    		n=0;
    		i +=1;
    		for (j=1 ; j<=i ; j++ )
    		{
    			if ( i%j == 0)
    			{
    				n +=1;			
    			}
    		}
    		if (n <=2 && n != 0)
    		{
    			myfile << c << "=\t"  << i <<"\n\n";
    			c +=1;
    		}
    		
    	}
    	myfile.close();
    	}else
    		cout << "Unable to open file";
    
    
      system("PAUSE");
    
    }

  6. #6
    2kaud's Avatar
    2kaud is offline Super Moderator Power Poster
    Join Date
    Dec 2012
    Location
    England
    Posts
    7,822

    Re: Prime Numbers

    Try this. I've kept your code structure but just made a couple of changes. It completes in a few seconds on my computer.

    Code:
    #include <iostream>
    #include <fstream>
    #include <string>
    #include <cstdlib>
    #include <cmath>
    using namespace std;
    
    int main()
    {
    long int	i = 1,
    		c = 2,
    		n,
    		s,
    		j;
    
    ofstream	myfile ("Prime.doc");
    
    	if (myfile.is_open()) {
    		myfile << 1 << "=\t"  << 2 <<"\n\n";
    
    		while (c <= 150000) {
    			n = 0;
    			i += 2;
    			s = (long)sqrt((float)i);
    			for (j = 3; j <= s; j+=2) {
    				if (i % j == 0) {
    					n += 1;			
    					break;
    				}
    			}
    
    			if (n == 0) {
    				myfile << c << "=\t"  << i <<"\n\n";
    				c += 1;
    			}
    		
    		}
    		myfile.close();
    	} else
    		cout << "Unable to open file";
    
    	return 0;
    }
    Last edited by 2kaud; May 14th, 2013 at 07:50 AM. Reason: Minor optimise change to algorithm / 1 is not a prime number
    All advice is offered in good faith only. All my code is tested (unless stated explicitly otherwise) with the latest version of Microsoft Visual Studio (using the supported features of the latest standard) and is offered as examples only - not as production quality. I cannot offer advice regarding any other c/c++ compiler/IDE or incompatibilities with VS. You are ultimately responsible for the effects of your programs and the integrity of the machines they run on. Anything I post, code snippets, advice, etc is licensed as Public Domain https://creativecommons.org/publicdomain/zero/1.0/ and can be used without reference or acknowledgement. Also note that I only provide advice and guidance via the forums - and not via private messages!

    C++23 Compiler: Microsoft VS2022 (17.6.5)

  7. #7
    Join Date
    May 2004
    Posts
    249

    Re: Prime Numbers

    Hey thanks buddy, it was complete in less then about 2 seconds on my mchine. so could you please explain as to what was wrong in my code/syntax. and i really appreciate your kind help..... I hope and i wish to learn more ways to improve on my coding from people like you.................... THanks a lot 2Kaud

  8. #8
    GCDEF is offline Elite Member Power Poster
    Join Date
    Nov 2003
    Location
    Florida
    Posts
    12,635

    Re: Prime Numbers

    Quote Originally Posted by rockx View Post
    Hey thanks buddy, it was complete in less then about 2 seconds on my mchine. so could you please explain as to what was wrong in my code/syntax. and i really appreciate your kind help..... I hope and i wish to learn more ways to improve on my coding from people like you.................... THanks a lot 2Kaud
    Why don't you watch them both run in the debugger and see what yours is doing compared to his.

  9. #9
    2kaud's Avatar
    2kaud is offline Super Moderator Power Poster
    Join Date
    Dec 2012
    Location
    England
    Posts
    7,822

    Re: Prime Numbers

    A prime number is a number that is only divisible by itself and 1. The only even prime number is 2. So the first prime numbers (2) can be output immediately. The first number to try for being prime is 3. As every even number is not prime (divisible by 2) then only odd numbers can be prime so the number to test is incremented by 2. If we are only testing odd numbers, then the division test loop can start at 3 and increment by 2 each time (as an odd number divided by an even number always has a remainder). As soon as the remainder is 0 then a non-prime number has been found and the division test loop can be exited. The upper bound for the division test loop is the sqrt of the number to be tested because if a factor is not found in that range that it won't be found in the full range as a number squared always has itself as a factor.

    As laserlight stated in post #2, there are other algorithms that can used to determine prime numbers (eg the sieve of Eratosthenes). Another way of thinking about a prime number is that a number is not prime if it is divisible by a prime number (except 1). So if a vector is created of prime numbers already found, then rather than having the division loop test all odd numbers from 3 to sqrt, it just tests all numbers already inserted into the prime vector. If a prime is found, then it is inserted into the vector. For large prime numbers with a suitable initial reserve size of the vector (to reduce memory re-allocation) this can be quite fast.

    PS As Eri523 and laserlight have pointed out, 1 is not a prime number. I was going to update this post before but lost internet connection whilst being upgraded to fibre. I will also amend the code.
    Last edited by 2kaud; May 14th, 2013 at 07:49 AM. Reason: 1 is not a prime number
    All advice is offered in good faith only. All my code is tested (unless stated explicitly otherwise) with the latest version of Microsoft Visual Studio (using the supported features of the latest standard) and is offered as examples only - not as production quality. I cannot offer advice regarding any other c/c++ compiler/IDE or incompatibilities with VS. You are ultimately responsible for the effects of your programs and the integrity of the machines they run on. Anything I post, code snippets, advice, etc is licensed as Public Domain https://creativecommons.org/publicdomain/zero/1.0/ and can be used without reference or acknowledgement. Also note that I only provide advice and guidance via the forums - and not via private messages!

    C++23 Compiler: Microsoft VS2022 (17.6.5)

  10. #10
    Join Date
    Jun 2010
    Location
    Germany
    Posts
    2,675

    Re: Prime Numbers

    Quote Originally Posted by 2kaud View Post
    A prime number is a number that is only divisible by itself and 1.
    Please note thar 1 is not a prime, i.e. rhe "and" in your sentence is to be interpreted in the sense of common human language understanding rather than the boolean sense (sort of "exclusive and"). One consequence, for instance, of 1 being a prime would be that the count of prime factors of a number (and the sum of factors) would be indeterminate, as one could always add any number of 1 factors.

    BTW, when it comes to speed, I really love the Sieve algorithm. ... though its memory demands may really complicate its use.
    I was thrown out of college for cheating on the metaphysics exam; I looked into the soul of the boy sitting next to me.

    This is a snakeskin jacket! And for me it's a symbol of my individuality, and my belief... in personal freedom.

  11. #11
    Join Date
    Jan 2006
    Location
    Singapore
    Posts
    6,765

    Re: Prime Numbers

    I was hoping that 2kaud would make the edit after replying to my PM instead of going somewhat off topic when someone else spotted the inclusion of 1 as a prime, but oh well...

    Quote Originally Posted by Eri523
    Please note thar 1 is not a prime, i.e. rhe "and" in your sentence is to be interpreted in the sense of common human language understanding rather than the boolean sense (sort of "exclusive and").
    Instead of re-interpreting, it would be simpler to impose a requirement for prime numbers to be greater than 1. Perhaps more accurately than what 2kaud wrote, we could say that a prime number is a positive integer that has exactly one positive integer divisor other than 1.

    Quote Originally Posted by Eri523
    One consequence, for instance, of 1 being a prime would be that the count of prime factors of a number (and the sum of factors) would be indeterminate, as one could always add any number of 1 factors.
    It might be better to just mention the fundamental theorem of arithmetic since it may not be obvious as to the signifance of such a count.

    Quote Originally Posted by Eri523
    I really love the Sieve algorithm.
    There's more than one sieve algorithm for finding prime numbers
    C + C++ Compiler: MinGW port of GCC
    Build + Version Control System: SCons + Bazaar

    Look up a C/C++ Reference and learn How To Ask Questions The Smart Way
    Kindly rate my posts if you found them useful

  12. #12
    Join Date
    Jun 2010
    Location
    Germany
    Posts
    2,675

    Re: Prime Numbers

    Quote Originally Posted by laserlight View Post
    [...] Perhaps more accurately than what 2kaud wrote, we could say that a prime number is a positive integer that has exactly one positive integer divisor other than 1.
    A pretty simple yet complete definition of primes we can perfectly settle on.

    It might be better to just mention the fundamental theorem of arithmetic since it may not be obvious as to the signifance of such a count.
    Actually, when researching for my post, I skipped the Fundamental Theorem section right to Primality Of One and based my post on that paragraph, thereby overlooking that the Fundamental Theorem practically says almost exactly what I wanted to express, juat on a solid scientific fundament... That's pobably because I usually prefer practical explanations about fundamental theorems when possible. (Yeah, not a really scientific attitude, I admit... In fact, the way I memorized for myself why 1 is not a prime is even more funky: It spoils the beauty of the prime factorization algorithm by introducing an extra special case. Even though, at implementation level, that probably wouldn't ever have any efficiency impact at all...)

    There's more than one sieve algorithm for finding prime numbers
    Really? Cool. I just knew the Eratosthenes algorithm until now. Do you have a link to some overview of Sieve algorithms? May make up a nice night reading on the tablet. (Oh, on second sight... Please don't over-interpret that last sentence. )
    I was thrown out of college for cheating on the metaphysics exam; I looked into the soul of the boy sitting next to me.

    This is a snakeskin jacket! And for me it's a symbol of my individuality, and my belief... in personal freedom.

  13. #13
    Join Date
    May 2004
    Posts
    249

    Re: Prime Numbers

    Now i have another problem. i have been entering pretty big numbers to calculate.....

    Somehow the other, the output file i got was over 512MB .doc file, and this failed the windows from opening the file. so whats the best file format i could be saving my output so that even if it is over a 1GB, i will still be able to see the result.


    Thanks again in advance

  14. #14
    Join Date
    Jan 2006
    Location
    Singapore
    Posts
    6,765

    Re: Prime Numbers

    It seems to me that a simple text format with one prime number per line should suffice.
    C + C++ Compiler: MinGW port of GCC
    Build + Version Control System: SCons + Bazaar

    Look up a C/C++ Reference and learn How To Ask Questions The Smart Way
    Kindly rate my posts if you found them useful

  15. #15
    Join Date
    Jun 2010
    Location
    Germany
    Posts
    2,675

    Re: Prime Numbers

    I have no idea of what you mean by "windows form" here, but at least the Windows standard text file editor Notepad fails way before the file sizes you demand. AFAICT its limit is 32 kB.

    That doesn't necessarily mean you need to change your output file format, though. Plain text is perfectly fine, basically. You just need an editor (or viewer) that's capable of handling your large files. One editor with this capability I use myself quite often is Notepad++. IIRC I have used it with files of quite a few MB, perhaps a few dozen. I can't tell its actual file size limit, but even that one may fail with giant files up to 1 GB. However, at this file size it would be hard to take for a human being to manually browse/edit a sequential file containing prime numbers anyway. (Uuuh, how boring... ) So with such a huge amount of primes, it's probably worth considering alternative approaches to data access. And that may make a change away from plain text format reasonable (probably away from any plain sequential file format, text or otherwise, at all.)
    I was thrown out of college for cheating on the metaphysics exam; I looked into the soul of the boy sitting next to me.

    This is a snakeskin jacket! And for me it's a symbol of my individuality, and my belief... in personal freedom.

Page 1 of 3 123 LastLast

Posting Permissions

  • You may not post new threads
  • You may not post replies
  • You may not post attachments
  • You may not edit your posts
  •  





Click Here to Expand Forum to Full Width

Featured