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

Thread: Prime Numbers

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

    Re: Prime Numbers

    Quote Originally Posted by rockx View Post
    I have got another question. the above code simply works fine. but is there any other way possible to further modify this
    Of course there is. Prime number generation is one of the most-researched subjects in computer sciences and mathematics, so there's plenty of other variations out there to study.

    This particular line does what its supposed to do:
    Code:
    if (i % j == 0)
    however, is there any way possible to replace 'j' wtih all the numbers that have actually been generated?
    What are you asking for? j already is being replaced with all candidate numbers to check for being an integral divider, time-sequentially within the loop.
    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.

  2. #32
    Join Date
    May 2004
    Posts
    249

    Re: Prime Numbers

    At the moment j consists of all integers, from 2 - sqrt(i). This is including all the calculated prime numbers as well as the composite numbers. So i m asking if j could be replaced with only the prime numbers so all the composite numbers between 2 and sqrt(i) is eliminated.

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

    Re: Prime Numbers

    In my original code, the j loop has bounds of 3 and sqrt(i) and increments by 2 to try every odd number.

    A prime number is not prime if it is divisible by a prime. The code could be modified so that when a prime is found it is added to a set container and the j loop could be replaced by an iteration of the set. Thus you would only be trying prime numbers and hence eliminate all the composite numbers.
    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)

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

    Re: Prime Numbers

    Quote Originally Posted by rockx View Post
    At the moment j consists of all integers, from 2 - sqrt(i). This is including all the calculated prime numbers as well as the composite numbers. So i m asking if j could be replaced with only the prime numbers so all the composite numbers between 2 and sqrt(i) is eliminated.
    Well, the elimination process you mention is just what your prime number code performs, i.e. what it's there for. If j would enumerate just the primes in the first place (maybe provided by some standard library algorithm or the like), there would be no need for your own prime number program at all.

    Or, perhaps, what you're really asking for is a quantum computer...
    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.

  5. #35
    Join Date
    Aug 2000
    Location
    New York, NY, USA
    Posts
    5,656

    Re: Prime Numbers

    Quote Originally Posted by Eri523 View Post
    Well, the elimination process you mention is just what your prime number code performs, i.e. what it's there for. If j would enumerate just the primes in the first place (maybe provided by some standard library algorithm or the like), there would be no need for your own prime number program at all.
    As I understood the suggestion, you can iterate through the list of ALREADY found prime numbers, than switch to the odd numbers above the last value.
    Vlad - MS MVP [2007 - 2012] - www.FeinSoftware.com
    Convenience and productivity tools for Microsoft Visual Studio:
    FeinWindows - replacement windows manager for Visual Studio, and more...

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

    Re: Prime Numbers

    Quote Originally Posted by 2kaud View Post
    In my original code, the j loop has bounds of 3 and sqrt(i) and increments by 2 to try every odd number.

    A prime number is not prime if it is divisible by a prime. The code could be modified so that when a prime is found it is added to a set container and the j loop could be replaced by an iteration of the set. Thus you would only be trying prime numbers and hence eliminate all the composite numbers.
    Try this

    Code:
    #include <fstream>
    #include <iostream>
    #include <cmath>
    #include <set>
    using namespace std;
    
    const char pfnam[] = "Prime.doc";
    
    typedef unsigned long int ULINT;
    
    typedef set<ULINT> setprimes;
    typedef setprimes::const_iterator pci;
    
    const ULINT maxprime = 150000;
    
    int main()
    {
    ULINT	pno = 0;
    
    setprimes primes;
    
    ofstream myfile (pfnam);
    
    	if (!myfile.is_open()) {
    		cout << "Unable to open file " << pfnam << endl;
    		return 1;
    	}
    
    	myfile << ++pno << "=\t"  << 2 <<"\n";
    
    	for (ULINT c = 3; c <= maxprime; c+=2) {
    		ULINT s = (ULINT)sqrt((long double)c);
    		bool notp = false;
    		for (pci pn = primes.begin(); pn != primes.end() && *pn <= s && !notp; ++pn) {
    			notp = (c % *pn == 0);
    		}
    
    		if (!notp) {
    			primes.insert(c);
    			myfile << ++pno << "=\t"  << c <<"\n";
    		}
    	}
    	myfile.close();
    
    	return 0;
    }
    Note that this method is memory intensive as the set primes holds all the previously found primes and when the outer c loop terminates, will contain all found primes.
    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. #37
    Join Date
    Jun 2010
    Location
    Germany
    Posts
    2,675

    Re: Prime Numbers

    Quote Originally Posted by VladimirF View Post
    As I understood the suggestion, you can iterate through the list of ALREADY found prime numbers, than switch to the odd numbers above the last value.
    Ah, ok, in this case I in deed misunderstood the question. Of course the primes calculated so far can be used to test for divisibility rather than each odd number up to the sqrt. And, given the program is to calculate the primes sequentially without skipping some (as all the proposals so far in this thread have been doing IIRC), falling back to odds instead of already calculated primes isn't even necessary: The overall prime density is about equal (can't tell the mathematical proof for that off the top of my head, though), so running out of already calculated primes in't expected to happen.
    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.

  8. #38
    Join Date
    May 2004
    Posts
    249

    Re: Prime Numbers

    Quote Originally Posted by Eri523 View Post
    Well, the elimination process you mention is just what your prime number code performs, i.e. what it's there for. If j would enumerate just the primes in the first place (maybe provided by some standard library algorithm or the like), there would be no need for your own prime number program at all.

    Or, perhaps, what you're really asking for is a quantum computer...
    Please let me rephrase my question. COuld it be possible for j to contain only the calculated Prime Numbers, no other numbers apart from the calculated numbers?

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

    Re: Prime Numbers

    Quote Originally Posted by rockx View Post
    Please let me rephrase my question. COuld it be possible for j to contain only the calculated Prime Numbers, no other numbers apart from the calculated numbers?
    Yes. See 2kaud's post #36. The variable in question isn't named j there, though.
    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 3 of 3 FirstFirst 123

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