1. ## 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. You are intending to use trial division, I presume?

Have you learnt about functions yet? 3. 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. 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. 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. 5. 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. 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. 7. 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! 8. Holy smokes! I lyk dat code. It makes me happy!  9. 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. 10. 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. Are these people playing a joke on me or what?! ;_;

Soma 12. 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. 13. 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. 14. 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. "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? Popular pages Recent additions 