473,883 Members | 1,527 Online

# Find prime numbers from a given number

1 New Member
Hi, can someone send me the algorithm for finding the products of prime numbers from a given number?

Thank You

Gary.
Oct 24 '06
11 46444
Banfa
9,065 Recognized Expert Moderator Expert
Except for 2 and 3 you only have to test for multiples of 6 plus or minus 1.
Until a potential divisor squared is larger than the number to be tested.
Or alternitively put you can skip every 3rd odd number because it is bound to be divisible by 3, and all even numbers because they are divisible by 2.

The question is can you code that efficiently (to which actually I think the answer is probably yes if you code it in the terms you have already given).
Apr 30 '07 #11
JosAH
11,448 Recognized Expert MVP
Or alternitively put you can skip every 3rd odd number because it is bound to be divisible by 3, and all even numbers because they are divisible by 2.

The question is can you code that efficiently (to which actually I think the answer is probably yes if you code it in the terms you have already given).
Yup, except for 2 and 3 you can do something like this:
Expand|Select|Wrap|Line Numbers
1. for (int d= 5, inc= 2; d*d <= n; )
2.    if (n%d == 0) // d is a factor
3.       n/= d; // if you want to find all factors;
4.    else {
5.       d+= inc; // next possible divisor
6.       inc= 6-inc; // next increment
7.    }
kind regards,

Jos
Apr 30 '07 #12