Page 1 of 2
How find prime factors of a given number using C++
Posted: Mon Apr 19, 2010 12:45 am
by 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);
}
}
Re: How find prime factors of a given number using C++
Posted: Mon Apr 19, 2010 1:07 am
by 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..
Re: How find prime factors of a given number using C++
Posted: Mon Apr 19, 2010 6:20 am
by 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.
Re: How find prime factors of a given number using C++
Posted: Tue Apr 20, 2010 12:03 am
by 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..
Re: How find prime factors of a given number using C++
Posted: Tue Apr 20, 2010 12:11 am
by 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.
Re: How find prime factors of a given number using C++
Posted: Tue Apr 20, 2010 8:12 pm
by 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
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)
Re: How find prime factors of a given number using C++
Posted: Wed Apr 21, 2010 5:48 am
by 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
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.
Re: How find prime factors of a given number using C++
Posted: Thu Apr 22, 2010 5:40 am
by ghostrider_gr
Saman wrote:
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...??
Re: How find prime factors of a given number using C++
Posted: Thu Apr 22, 2010 3:01 pm
by 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.
Re: How find prime factors of a given number using C++
Posted: Tue Apr 27, 2010 4:16 am
by 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");
}