# Math Help - factorization of number

1. ## factorization of number

I have written a C code program for factorization of a given number into two divisors, when the two divisors are having approximately the same number of digits . It cannot check for prime numbers.

With my code limit I can check it only upto 14 digits using long long int. It is working perfectly upto these 14 digits (condition is the two divisors must have app the same no.of.digits). Bigger than 14 digits it is yielding wrong answers.

because it is a math forum, I like to post the code here. So that someone can check its efficiency for large numbers.

If anyone's idea is to use GMP libray, I have already installed gmp using msys, and had written a C code program using gmp. The problem I faced is, when I compiled the program , it compiled perfectly. But when I selected to Run the code, It says "Project is stopped working". The problem is in input and output code lines i.e., I used printf and scanf functions to get o/p and i/p.
To avoid this problem I did not find any best tutorial on GMP. And I did not understand what he is saying about the o/p and i/p functions, in the Documentation of GMP-5.0.1.
If you accept to post the code using gmp , I will post that also.

Thankful for the forum mentors and moderators and users , and for any replies given.

Code:
#include<stdio.h>
#include<conio.h>
#include<math.h>
#include<process.h>
#include <time.h>
main()
{
time_t result;
long long int a,b=0,x=0,y=0,z=0,c,c1,d,e,f,p,n1n2,l=0,p4,p7,p8,p9,disc;
double t=2,n11,m[100],p6,p5=1,p11=1,x1,x2,p1,p2;
double sqtr();

FILE *filea1b_3 = fopen("filea1b_3.txt" , "w");
printf("Enter the value of P : ");
scanf("%I64u",&p);
printf("So , Given P = %I64u . \n\n\n\n",p);
fprintf(filea1b_3, "So , Given P = %I64u . \n",p);
p1=sqrt(p);
p4=p1;
p6=p1-p4;
if(p6>0)
{
for(a=2;(p5&&p11)>0;a++)
{
x++;
f=a*a;
for(b=1;b<f;b++)
{
if((p-b)%a==0)
{
y++;
n11=(((p+b)-(sqrt(4*p*b)))/(a*a));
p4=n11;
p5=n11-p4;
p6=n11-p5;
p7=p6;
for(c=1;c<=(b/2);c++)
{
if(b%c==0)
{
z++;
c1=(b/c);

disc=((b+(a*a*p7)-p)*(b+(a*a*p7)-p))-(4*a*c*a*p7*(b/c));/*to find discriminant*/
if(disc>0)/*distinct roots*/
{
x1=(p-b-(a*a*p7)+sqrt(disc))/(2*a*(b/c));
x2=(p-b-(a*a*p7)-sqrt(disc))/(2*a*(b/c));
}
if(disc==0)/*Equal roots*/
{
x1=x2=(p-b-(a*a*p7))/(2*a*c);
}
if(disc<0)
{
x1=(p-b-(a*a*p7))/(2*a*c);/*complex roots*/
x2=sqrt(fabs(disc))/(2*a*c);
}
p4=x1;
p5=x1-p4;
p6=x1-p5;
p8=p6;
p4=x2;
p11=x2-p4;
p6=x2-p11;
p9=p6;
if((p5==0)||(p11==0))
{
n1n2=x1*x2;
d=x+y+z;
e=(p-b)/a;
printf("\n\nNo.of.loops = %I64u\n",d);
printf("a = %I64u, b= %I64u, N = %I64u, N1 = %f, N2 = %f, N1N2 = %I64u",a,b,e,x1,x2,n1n2);
printf("\n\nb1 = %d and b2 = %d (or) b1 = %d and b2 = %d\n\n",c,c1,c1,c);
fprintf(filea1b_3, "\n\nNo.of.loops = %I64u\n",d);
fprintf(filea1b_3, "a = %I64u, b= %I64u, N = %I64u, N1 = %f, N2 = %f, N1N2 = %I64u",a,b,e,x1,x2,n1n2);
fprintf(filea1b_3, "\n\nb1 = %d and b2 = %d (or) b1 = %d and b2 = %d\n\n",c,c1,c1,c);
getch();
exit(0);
}
}
}
if((p5==0)||(p11==0))
{
exit(0);
}
b=b+a-1;
}
}
}
}
else
{
printf(" Given number is a perfect square");
printf(" P = %f^2 ",p1);
fprintf(filea1b_3, " Given number is a perfect square");
fprintf(filea1b_3, " P = %f^2 ",p1);
}
getch();
}

As I said the two divisors should be closer to each other in terms of no.of.digits. This will give one factor and the other will be given number divided by the above obtained factor. It will not work on prime numbers.

here factor is (aN1+b1) if we got N1 as an integer . or (aN2+b1) if we got N2 as an integer.
Here b1 = anyone of the b1 values we got in the answer.

Any replies given will be helpful to me . thanks.

2. Originally Posted by ssnmanikanta
I have written a C code program for factorization of a given number into two divisors, when the two divisors are having approximately the same number of digits . It cannot check for prime numbers.

With my code limit I can check it only upto 14 digits using long long int. It is working perfectly upto these 14 digits (condition is the two divisors must have app the same no.of.digits). Bigger than 14 digits it is yielding wrong answers.

because it is a math forum, I like to post the code here. So that someone can check its efficiency for large numbers.

If anyone's idea is to use GMP libray, I have already installed gmp using msys, and had written a C code program using gmp. The problem I faced is, when I compiled the program , it compiled perfectly. But when I selected to Run the code, It says "Project is stopped working". The problem is in input and output code lines i.e., I used printf and scanf functions to get o/p and i/p.
To avoid this problem I did not find any best tutorial on GMP. And I did not understand what he is saying about the o/p and i/p functions, in the Documentation of GMP-5.0.1.
If you accept to post the code using gmp , I will post that also.

Thankful for the forum mentors and moderators and users , and for any replies given.

Code:
#include<stdio.h>
#include<conio.h>
#include<math.h>
#include<process.h>
#include <time.h>
main()
{
time_t result;
long long int a,b=0,x=0,y=0,z=0,c,c1,d,e,f,p,n1n2,l=0,p4,p7,p8,p9,disc;
double t=2,n11,m[100],p6,p5=1,p11=1,x1,x2,p1,p2;
double sqtr();

FILE *filea1b_3 = fopen("filea1b_3.txt" , "w");
printf("Enter the value of P : ");
scanf("%I64u",&p);
printf("So , Given P = %I64u . \n\n\n\n",p);
fprintf(filea1b_3, "So , Given P = %I64u . \n",p);
p1=sqrt(p);
p4=p1;
p6=p1-p4;
if(p6>0)
{
for(a=2;(p5&&p11)>0;a++)
{
x++;
f=a*a;
for(b=1;b<f;b++)
{
if((p-b)%a==0)
{
y++;
n11=(((p+b)-(sqrt(4*p*b)))/(a*a));
p4=n11;
p5=n11-p4;
p6=n11-p5;
p7=p6;
for(c=1;c<=(b/2);c++)
{
if(b%c==0)
{
z++;
c1=(b/c);

disc=((b+(a*a*p7)-p)*(b+(a*a*p7)-p))-(4*a*c*a*p7*(b/c));/*to find discriminant*/
if(disc>0)/*distinct roots*/
{
x1=(p-b-(a*a*p7)+sqrt(disc))/(2*a*(b/c));
x2=(p-b-(a*a*p7)-sqrt(disc))/(2*a*(b/c));
}
if(disc==0)/*Equal roots*/
{
x1=x2=(p-b-(a*a*p7))/(2*a*c);
}
if(disc<0)
{
x1=(p-b-(a*a*p7))/(2*a*c);/*complex roots*/
x2=sqrt(fabs(disc))/(2*a*c);
}
p4=x1;
p5=x1-p4;
p6=x1-p5;
p8=p6;
p4=x2;
p11=x2-p4;
p6=x2-p11;
p9=p6;
if((p5==0)||(p11==0))
{
n1n2=x1*x2;
d=x+y+z;
e=(p-b)/a;
printf("\n\nNo.of.loops = %I64u\n",d);
printf("a = %I64u, b= %I64u, N = %I64u, N1 = %f, N2 = %f, N1N2 = %I64u",a,b,e,x1,x2,n1n2);
printf("\n\nb1 = %d and b2 = %d (or) b1 = %d and b2 = %d\n\n",c,c1,c1,c);
fprintf(filea1b_3, "\n\nNo.of.loops = %I64u\n",d);
fprintf(filea1b_3, "a = %I64u, b= %I64u, N = %I64u, N1 = %f, N2 = %f, N1N2 = %I64u",a,b,e,x1,x2,n1n2);
fprintf(filea1b_3, "\n\nb1 = %d and b2 = %d (or) b1 = %d and b2 = %d\n\n",c,c1,c1,c);
getch();
exit(0);
}
}
}
if((p5==0)||(p11==0))
{
exit(0);
}
b=b+a-1;
}
}
}
}
else
{
printf(" Given number is a perfect square");
printf(" P = %f^2 ",p1);
fprintf(filea1b_3, " Given number is a perfect square");
fprintf(filea1b_3, " P = %f^2 ",p1);
}
getch();
}

As I said the two divisors should be closer to each other in terms of no.of.digits. This will give one factor and the other will be given number divided by the above obtained factor. It will not work on prime numbers.

here factor is (aN1+b1) if we got N1 as an integer . or (aN2+b1) if we got N2 as an integer.
Here b1 = anyone of the b1 values we got in the answer.

Any replies given will be helpful to me . thanks.
Try commenting your code, sort out the indentation and post the algorithm you think this implements.

CB

3. The number may be too large for long long int. long long int is a non-standard data type and it is not guaranteed to work on all compilers. What does your computer give you with this code?
Code:
int size = sizeof (long long int);
printf ("%i", size);
If it gives you 8 you should be fine up to 15 digit numbers according to here.

4. Originally Posted by Jskid
The number may be too large for long long int. long long int is a non-standard data type and it is not guaranteed to work on all compilers. What does your computer give you with this code?
Code:
int size = sizeof (long long int);
printf ("%i", size);
If it gives you 8 you should be fine up to 15 digit numbers according to here.
That link does not mention a "long long int" nor any 8 byte integer types. What you seem to be referring to is the precision of a double precision float for your 15 decimal digits.

You can use double precision floats to hold integer values but you have effectively 52 or 53 bits (you can do the same trick with wider float types, but these are not exactly standardised yet).

Of course this could always be recoded in a system that supports arbitrary precision arithmetic, such as a CAS, or you could use the extended/arbitrary precision libraries available for C++/Java.

CB

5. When I run the code on my computer I get 8 bytes. The website says that should be about a 15 digit number in binary notation. However on the OP's computer a long long int may not be 8 bytes.

6. Originally Posted by Jskid
When I run the code on my computer I get 8 bytes. The website says that should be about a 15 digit number in binary notation. However on the OP's computer a long long int may not be 8 bytes.
The longest signed integer representable in 64 bits is $2^{64}-1$ which will give ~18-19 decimal digits (but there is no such standardised type IIRC), the 15 you mention corresponds to the 52 bit mantissa of a double (float)

CB