Finding smallest prime divider of NUM

[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]

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

[ziggystarman]

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

[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]

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!