# Prime numbers

Show 80 post(s) from this thread on one page
Page 1 of 2 12 Last
• 12-11-2008
whiterebbit
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;             }         }     } }```
• 12-11-2008
laserlight
You are intending to use trial division, I presume?

Have you learnt about functions yet?
• 12-11-2008
whiterebbit
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.
• 12-11-2008
laserlight
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.
• 12-11-2008
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.
• 12-11-2008
laserlight
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.
• 12-11-2008
execute
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!
• 12-11-2008
c++0x
Holy smokes! I lyk dat code. It makes me happy! :)
• 12-11-2008
Cogman
Quote:

Originally Posted by execute
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.
• 12-11-2008
c++0x
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.
• 12-11-2008
phantomotap
Are these people playing a joke on me or what?! ;_;

Soma
• 12-11-2008
execute
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.
• 12-11-2008
abachler
Quote:

Originally Posted by execute
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.
• 12-11-2008
phantomotap
Quote:

I believe what execute means is that it is the most efficient non-sieve algorithm.
O_o

Quote:

That would not make it any faster.
o_O

Quote:

I timed it.
O_o

Quote:

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

Quote:

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

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

Soma
• 12-11-2008
execute
"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?
Show 80 post(s) from this thread on one page
Page 1 of 2 12 Last