How find prime factors of a given number using C++

[Saman]

You can use the following code to do this.

Code: Select all

void find_primeFactors(int x){

	int i = 3, r = x;

	while (!(r & 1)) {
		printf("2\n");
		r >>= 1;
	}

	while (i <= (sqrt(r)+1)) {
		if ((r % i) == 0) {
			printf("%ld\n",i);
			r/=i;
		}
		else{
			i+=2;
		}
	}

	if (r > 1){
		printf("%ld\n", r);
	}
}

[ghostrider_gr]

in order not to open new thread.. is this algorithm sufficient for large numbers?? for ie for n= 100.000.000..

i have found other algorithms such as quadratic sieve but i don't understand them so as to transfer them into code.. if anyone has heard them, can explain them?? thanks anyway..

[Saman]

Since we use int as the data type, the largest possible number would be 2,147,483,647

If you use unsigned int instead of all int in code, the maximum number would be 4,294,967,295

If you are in Windows, then you can use a data type called __int64 which the highest possible number is 9,223,372,036,854,775,807

If you use unsigned __int64, then the largest number it can hold would be 18,446,744,073,709,551,615

If you use __int64, then you have to change the printf statements to suit the data type as explained here: How to print unsigned __int64 using printf

See http://msdn.microsoft.com/en-us/library ... S.80).aspx for more details.

[ghostrider_gr]

thanks.. but at this time this is not my primary problem.. i will deal with it later..

what i have to do in the project is find for any number between 1 and 100.000.000 its largest prime factor..

what i ve done is construct a linked list of all the prime numbers and then check it's one number between 1 and 100.000.000 to find if its largest prime factor by starting dividing with the primes found above..

but i would appreciate if there are any ideas of making it faster than that (thats why i mentioned quadratic sieves that i found on the web- but i dont know if its faster for finding prime factors).. thanks..

[Saman]

Your method is definitely inefficient.
If follow the logic in the above code, you can see that last number it creates is the largest prime factor of the given number.
You can define a variable as last_factor and always set this at printing lines. At the end of execution of the function, what you have on that variable is the largest prime factor.

And it outputs the number within a second.

[ghostrider_gr]

well i am not familiar with c++ but think i have understood the code above:

i don't get that point of the code

Code: Select all

while (!(r & 1)) {
      printf("2\n");
      r >>= 1;
   }

and another one question:

why

Code: Select all

i=i+2

and not proceed to the next prime.. because by adding 2 , you will also examine numbers that are not prime..

in general, my idea is that:
start from sqrt(n) down to 2, and starting dividing with the prime numbers.. the firsi with mod=0 one is the largest.. (supposed that i have the primes in an array or in a list)

[Saman]

i don't get that point of the code

Code: Select all

    while (!(r & 1)) {
          printf("2\n");
          r >>= 1;
       }

This code is used to extract all 2s from the number.

(r & 1) is true is r is an odd number. (& is the bitwise AND operator in C).
!(r & 1) is used to check whether r is an even number. (Since ! is used for NOT)
If it is even -> it is divisible by 2.
r >>= 1; this is right shift by 1 operation which is equals to r = r / 2

After this loop, r becomes a odd number.

and another one question:

why

Code: Select all

    i=i+2

and not proceed to the next prime.. because by adding 2 , you will also examine numbers that are not prime..

This is because, we need i to be odd numbers... i starts from 3, then we make it 5, 7, 9, 11 ......
Since we have extracted all 2s from the original number, there is no point in making it a even number.

[ghostrider_gr]

This is because, we need i to be odd numbers... i starts from 3, then we make it 5, 7, 9, 11 ......
Since we have extracted all 2s from the original number, there is no point in making it a even number.

but why not to extract alla the 3's,5's...that's why i mentioned use a list of prime factors...

let me asky you sth else.. any idea for that: if i want to find alla the numbers between ,lets say 1 and 100.000.000 whose largest prime factor is less than 1024...??

[Saman]

but why not to extract alla the 3's,5's...that's why i mentioned use a list of prime factors...

You can have an array of primes to be used for i. There is no argument.
The point is, what could be the largest prime factor which is going to be a factor of the arbitrary number.
If you can decide on this, you can use a static array (with fixed number of elements).

let me asky you sth else.. any idea for that: if i want to find alla the numbers between ,lets say 1 and 100.000.000 whose largest prime factor is less than 1024...??

You can do that quite easily by calling the prime factor function on the first post repeatedly for numbers between 0 to N.
Modify the function to return the largest prime for each number so that you can check whether that is less the 1024 or anything and store them in an array. That will give you the list you need in an array at the end of execution.

It seems to me the first thing you should do is to make the function working in whatever language you need...(C, Java, C#, Etc...). When you see the output, you can change/improve it as you need.

[ghostrider_gr]

ok.. can you tell me what is wrong with the code below..

Code: Select all

#include <stdio.h>
#include <stdlib.h>

int main () {
    int flag=1,B=1024,n=1,count=3,flag1;
    
    struct primes {
           int no;
           struct primes * next;
};

typedef struct primes PrimesList;

PrimesList *list,*temp, *initial;

list=(PrimesList*)malloc(sizeof(PrimesList));
temp=list;
temp->no=2;
temp->next=(PrimesList*)malloc(sizeof(PrimesList));
temp=temp->next;
temp->next=NULL;
temp->no=3;
temp->next=(PrimesList*)malloc(sizeof(PrimesList));
temp=temp->next;
temp->next=NULL;
temp->no=5;
temp->next=(PrimesList*)malloc(sizeof(PrimesList));
temp=temp->next;
temp->next=NULL;

int start=7;
int i=start;
while (i<=B) {
    initial=list;
    flag1=0;
    while ( ((initial->next)!= NULL) && (flag1==0) ) {
          if ((i% initial->no)==0) flag1=0;
          else initial=initial->next;
    }
    if (flag1=0) {
       temp->next= (PrimesList*)malloc(sizeof(PrimesList));
       temp=temp->next;
       temp->no=i;
       temp->next=NULL;
       count=count+1;
    }
    i=i+2;
}

temp=list;

while ((temp->next)!= NULL ) {
      printf("%d next: \n ",temp->no);
      temp=temp->next;
}
printf("total: %d",count);
temp=list;

system("pause");

}