Dixon 's Factorization Method with implementation | C ++ implementation of Dixon factorization algo ; Function to find the factors of a number using the Dixon Factorization Algorithm ; Factor base for the given number ; Starting from the ceil of the root of the given number N ; Storing the related squares ; For every number from the square root Till N ; Finding the related squares ; If the two numbers are the related squares , then append them to the array ; For every pair in the array , compute the GCD such that ; If we find a factor other than 1 , then appending it to the final factor array ; Driver Code
#include <bits/stdc++.h> NEW_LINE using namespace std ; #include <vector> NEW_LINE void factor ( int n ) { int base [ 4 ] = { 2 , 3 , 5 , 7 } ; int start = int ( sqrt ( n ) ) ; vector < vector < int > > pairs ; int len = sizeof ( base ) / sizeof ( base [ 0 ] ) ; for ( int i = start ; i < n ; i ++ ) { vector < int > v ; for ( int j = 0 ; j < len ; j ++ ) { int lhs = ( ( int ) pow ( i , 2 ) ) % n ; int rhs = ( ( int ) pow ( base [ j ] , 2 ) ) % n ; if ( lhs == rhs ) { v . push_back ( i ) ; v . push_back ( base [ j ] ) ; pairs . push_back ( v ) ; } } } vector < int > newvec ; len = pairs . size ( ) ; for ( int i = 0 ; i < len ; i ++ ) { int factor = __gcd ( pairs [ i ] [ 0 ] - pairs [ i ] [ 1 ] , n ) ; if ( factor != 1 ) newvec . push_back ( factor ) ; } set < int > s ; for ( int i = 0 ; i < newvec . size ( ) ; i ++ ) s . insert ( newvec [ i ] ) ; for ( auto i = s . begin ( ) ; i != s . end ( ) ; i ++ ) cout << ( * i ) << " ▁ " ; } int main ( ) { factor ( 23449 ) ; }