finding out prime-numbers

[DannyGT]

Hi all,
I have a number and I would like to find out which two prime numbers I have to put together to get this number. For small numbers my algorithm works just fine but for bigger it is to slow.

I use sqrt() and then I increase this number always by 1 and trying to find out if it is a prime number by dividing numbers from 2 to number I get from sqrt(). If I get a prime number, I divide my number with this prime number and then I test the outcome number if it is prime number.

Is there any way how to find out prime number faster??

Sorry I didn't posted the source code but I would have to translate it all to English... and I think it is not so complex problem.

Thanks

[kevinchkin]

which two prime numbers I have to put together to get this numbe

This is not very clear to me, what do you mean when you say put together?

[DannyGT]

Sorry... for example
I get 15 and I would like to find which two prime numbers multiply to get 15

15 = 3 * 5

this is easy but this

282943 = 541 * 523

take much more time...

[buffbill]

Try doing it recursively with something like:

int n ;  // Assume n is the number to factor
while(n)
  {
    cout<<"\nEnter an integer ";
    cin>>n;
    cout<<"The factors of "<<n<<" are ";
    int lastFactor = 2;
       while( lastFactor < n ) 
       {
          if( n % lastFactor == 0 ) 
           { cout << lastFactor << ' ';
               n /= lastFactor;
           } else 
          ++lastFactor;//tail recursion
       }

     if( n != 1 )
      cout << n;
  }

[elvis]

I would do it like this:
(1) build a map of prime numbers, for instance the first 10,000 primes or so
(2) multiply each prime with each higher prime to get a map <int, pair<int, int>> of all products
thsi map will have a couple of million elements, which is nothing on current compuetrs
(3) for any number you want to check, locate it in the map (2), and you find immediately
which two prime numbers multiply into that number. If your number does not exist
in the map, there are no two prime numbers that multiply into the target

If you need to test a lot of numbers, this method is probably quicker than any algorithmic
approach you try, because all the work is now done just once, and then you can just look
up numbers of interest in the map