## Despairy

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!

## Momerath 1,327

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

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

## ziggystarman 12

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

commented: 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 +0

## Despairy

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!

## vijayan121 1,152

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/

## Despairy

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!