im looking for a more efficient algorithm,
is there any known one? ive checked my math books and c++ book
and really didnt find anything more efficient than the following :

``````int first_prime(int num)
{
for (int i=2;i<sqrt(num);i++)
{
if (num%i==0)
{
if (isprime(i));
return(i);
}
}
}

bool isprime(int prime)
{
for (int i=2;i<sqrt(prime);i++)
{
if (prime%i==0)
return(false);
}
return(true);
}``````

thank, good day!

4
Contributors
5
Replies
13
Views
7 Years
Discussion Span
Last Post by Despairy

You could speed it up a bit by checking if 2 is a divisor, then if not go into a loop starting at 3 and incrementing by 2. There is also no need to check if the divisor is prime as the first divisor you find will always be prime. Think about it

Edited by Momerath: n/a

thanks for your help, hoped for like a huge math algorithm that saves lots of time ;) but thats cool also ty

& there are a few posts about primes in these forums.

if your just trying to get more posts dont do it in my posts cuz i use the search function and didnt find any effective algorithm niether on wikipedia . have a nice day

oh... that sounds right... dohh
so i guess this function is enough

``````int first_prime(int num)
{
if (num%2==0)
return(2);
for (int i=3;i<sqrt(num);i+=2)
{
if (num%i==0)
return(i);
}
return(num);
}``````

cool thanks for that!

A simple, reasonably fast algorithm to find the smallest prime factor of a number N would be:

a. generate all prime numbers up to the square root of N using a sieve algorithm.

b. the first (smallest) generated prime number that divides N is the smallest prime factor.

For example:

``````#include <vector>
#include <algorithm>
#include <iostream>

// sieve of sundaram (naive implementation)
std::vector<int> primes_upto( int N )
{
const int M = N / 2 ;
std::vector<bool> sieve( M, true ) ;
for( int i = 1 ; i < M ; ++i )
{
const int L = (M-i) / ( 2*i + 1 ) ;
for( int j = i ; j <= L ; ++j )
sieve[ i + j + 2*i*j ] = false ;
}

std::vector<int> primes ;
primes.push_back(2) ;
for( int i = 1 ; i < M ; ++i )
if( sieve[i] ) primes.push_back( i*2 + 1 ) ;
return primes ;
}

int smallest_prime_factor( int N )
{
if( N < 2 ) return N ;

std::vector<int> primes = primes_upto( std::sqrt(N) + 1 ) ;
for( std::vector<int>::size_type i = 0 ; i < primes.size() ; ++i )
if( ( N % primes[i] ) == 0 ) return primes[i] ;

return N ;
}``````

For large numbers (up to about 2^70 or so), the Brent-Pollard Rho algorithm is said to be the fastest.
http://en.wikipedia.org/wiki/Pollard%27s_rho_algorithm#Variants
http://www.remcobloemen.nl/2009/12/brent-pollard-%CF%81-factorisation/

great thanks! this is exactly what i meant!
only problem is that we didnt study the vectors
yet,besides linear math class. so no idea what it acctualy
looks like on the c++ programs
anyway time to turn to the book thanks again!