Thread: Prime numbers

  1. #1
    Registered User
    Join Date
    Dec 2008
    Posts
    8

    Prime numbers

    My code is written to find prime numbers from 2 to num. The code outputs every value of x, once if it is prime and more if it is not. I would like to know how to just output prime numbers. I am new to programming so please explain what your new bits of code does.

    Code:
    #include <iostream>
    using namespace std;
    
    int main()
    
    {
    
        int num=23;
    
        for ( int x=1 ; x<num ; x++)
        {
            for ( int y = 2; y<=x ; y++)
            {
                if ( x % y == 0 )
                {
                   cout<< x <<endl;
                }
            }
        }
    }

  2. #2
    C++ Witch laserlight's Avatar
    Join Date
    Oct 2003
    Location
    Singapore
    Posts
    28,412
    You are intending to use trial division, I presume?

    Have you learnt about functions yet?
    Quote Originally Posted by Bjarne Stroustrup (2000-10-14)
    I get maybe two dozen requests for help with some sort of programming or design problem every day. Most have more sense than to send me hundreds of lines of code. If they do, I ask them to find the smallest example that exhibits the problem and send me that. Mostly, they then find the error themselves. "Finding the smallest program that demonstrates the error" is a powerful debugging tool.
    Look up a C++ Reference and learn How To Ask Questions The Smart Way

  3. #3
    Registered User
    Join Date
    Dec 2008
    Posts
    8
    Hello again laserlight cheers for your help. I am doing Project Euler problems to learn c++ the current problem is:

    The prime factors of 13195 are 5, 7, 13 and 29.

    What is the largest prime factor of the number 600851475143 ?

    I trying to learn by doing I have read http://www.cprogramming.com/tutorial/lesson4.html on functions and played about by it so a function would be great to include in this program.

    Sorry I dont know what a trial division is.

  4. #4
    C++ Witch laserlight's Avatar
    Join Date
    Oct 2003
    Location
    Singapore
    Posts
    28,412
    Quote Originally Posted by whiterebbit
    Sorry I dont know what a trial division.
    Trial division is a primality testing algorithm that proves that an integer greater than 1 is prime by showing that it is not divisible by all primes not greater than the integer's square root. Of course, if the integer is divisible by any such prime, then it must be composite.

    Quote Originally Posted by whiterebbit
    What is the largest prime factor of the number 600851475143 ?
    You could use a similiar approach: find the smallest prime that divides the number by testing all primes (or primes and composites) no greater than the square root of the number to see if they perfectly divide the number. If no such prime is found, then the number itself is it largest prime factor. Else, divide the number by the first prime factor found (i.e., the smallest prime factor). If the quotient is prime, then it must be the largest prime factor, otherwise you need to analyse it further. Use the fundamental theorem of arithmetic to help in your analysis.
    Quote Originally Posted by Bjarne Stroustrup (2000-10-14)
    I get maybe two dozen requests for help with some sort of programming or design problem every day. Most have more sense than to send me hundreds of lines of code. If they do, I ask them to find the smallest example that exhibits the problem and send me that. Mostly, they then find the error themselves. "Finding the smallest program that demonstrates the error" is a powerful debugging tool.
    Look up a C++ Reference and learn How To Ask Questions The Smart Way

  5. #5
    Malum in se abachler's Avatar
    Join Date
    Apr 2007
    Posts
    3,195
    Or you could start the search at the sqrt() of the number and checck each prime number goin down until you eithe rfind one that it is divisible by or reach 1, in which case the number is prime and its own greatest factor.

  6. #6
    C++ Witch laserlight's Avatar
    Join Date
    Oct 2003
    Location
    Singapore
    Posts
    28,412
    Quote Originally Posted by abachler
    Or you could start the search at the sqrt() of the number and checck each prime number goin down until you eithe rfind one that it is divisible by or reach 1, in which case the number is prime and its own greatest factor.
    Are you sure that would give the largest prime factor? Overall, the problem sounds more like a factoring problem than a primality testing problem.
    Quote Originally Posted by Bjarne Stroustrup (2000-10-14)
    I get maybe two dozen requests for help with some sort of programming or design problem every day. Most have more sense than to send me hundreds of lines of code. If they do, I ask them to find the smallest example that exhibits the problem and send me that. Mostly, they then find the error themselves. "Finding the smallest program that demonstrates the error" is a powerful debugging tool.
    Look up a C++ Reference and learn How To Ask Questions The Smart Way

  7. #7
    Registered User
    Join Date
    Apr 2006
    Posts
    137
    Here's the MOST efficient C++ Prime Number Algorithm.

    I coded it and timed it versus other prime number generators.
    It uses sqrt as well!
    ★ Inferno provides Programming Tutorials in a variety of languages. Join our Programming Forums. ★

  8. #8
    Banned
    Join Date
    Dec 2008
    Location
    Maputo, Mozambique
    Posts
    82
    Holy smokes! I lyk dat code. It makes me happy!

  9. #9
    Registered User
    Join Date
    Jun 2008
    Posts
    62
    Quote Originally Posted by execute View Post
    Here's the MOST efficient C++ Prime Number Algorithm.

    I coded it and timed it versus other prime number generators.
    It uses sqrt as well!
    That's NOT the MOST efficient prime number generator. I've made faster easily. A more efficient generator keeps track of previous primes and test the current prime against those primes rather then trying to test against every odd number.

  10. #10
    Banned
    Join Date
    Dec 2008
    Location
    Maputo, Mozambique
    Posts
    82
    I believe what execute means is that it is the most efficient non-sieve algorithm. But I hate to put words into the mouths of others. Cuz dats jus meen.

  11. #11
    Master Apprentice phantomotap's Avatar
    Join Date
    Jan 2008
    Posts
    5,108
    Are these people playing a joke on me or what?! ;_;

    Soma
    Last edited by phantomotap; 12-11-2008 at 05:08 PM.

  12. #12
    Registered User
    Join Date
    Apr 2006
    Posts
    137
    That would not make it any faster. I timed it.
    Odd numbers are faster up to the sqrt of the function is the best way.

    I'm sure someone may think of a more genius method being really good at math, but it's not likely, and until I see a code of something faster, you can't make that argument.
    ★ Inferno provides Programming Tutorials in a variety of languages. Join our Programming Forums. ★

  13. #13
    Malum in se abachler's Avatar
    Join Date
    Apr 2007
    Posts
    3,195
    Quote Originally Posted by execute View Post
    That would not make it any faster. I timed it.
    Odd numbers are faster up to the sqrt of the function is the best way.

    I'm sure someone may think of a more genius method being really good at math, but it's not likely, and until I see a code of something faster, you can't make that argument.

    check out the prime number generator contest in the contest channel, there are at least half a dozen faster algorithms posted there.

  14. #14
    Master Apprentice phantomotap's Avatar
    Join Date
    Jan 2008
    Posts
    5,108
    I believe what execute means is that it is the most efficient non-sieve algorithm.
    O_o

    That would not make it any faster.
    o_O

    I timed it.
    O_o

    Odd numbers are faster up to the sqrt of the function is the best way.
    o_O

    I'm sure someone may [...] can't make that argument.
    O_o

    Okay. I get it. Haha. Jokes on Zero... ;_;

    Soma

  15. #15
    Registered User
    Join Date
    Apr 2006
    Posts
    137
    "most efficient non-sieve algorithm" This is correct, that's what I meant by fastest, didn't know anyone would use that sort of method. I looked in contest forum, yes if you did all that work with an algorithm it will be faster, but I never thought anyone would use that long a method for something as simple as prime numbers . I misunderstood what Cogman meant, I was thinking of another method.

    Why are you spamming phantom?
    ★ Inferno provides Programming Tutorials in a variety of languages. Join our Programming Forums. ★

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Logical errors with seach function
    By Taka in forum C Programming
    Replies: 4
    Last Post: 09-18-2006, 05:20 AM
  2. Replies: 18
    Last Post: 11-04-2005, 02:41 PM
  3. prime numbers, counters, help!
    By vege^ in forum C++ Programming
    Replies: 1
    Last Post: 03-10-2003, 04:32 PM
  4. Prime numbers
    By Lazy Student in forum C Programming
    Replies: 12
    Last Post: 05-14-2002, 05:53 AM
  5. Homework help
    By Jigsaw in forum C++ Programming
    Replies: 2
    Last Post: 03-06-2002, 05:56 PM