problem with large numbers

[saurav]

Hello,
I am trying to develop a c++ program that would, given any integer, decide whether it is prime. My program responds for small numbers, but doesn't if the number is great enough!

Consider this code, which is very basic, and which responds for n=11117, but falls through (hangs) for 111127

#include<iostream>
#include<cmath>
using namespace std;
bool divisibility(int i,int j)
{float k; k=float(j);
if(i==0) return false;
else if(j/i ==k/i) return true;
else return false;}

int gcd(int i,int j)
{ 
if(divisibility(i,j)==true) return i;
else if(divisibility(j,i)==true) return j;
else if(i==1||j==1) return 1;
else    {
	int k,l; if(j<i) k=j;else k=i;
	
	if(k>0)
		{while(k>0)
		{if(divisibility(k,i)==true&&divisibility(k,j)==true) return k;
		else k--;}				
		}
	else return 1;
	}
}




bool coprime(int i,int j)
{if(gcd(i,j)==1) return true;
else return false;}



bool primeness(int n)
{int i;
if(n>1)
{int i=1; if((i-1)<n/2){while((i-1)<=n/2){if(coprime(i,n)==true){if((i-1)==n/2)return true;else i++;}else return false;}}}
else return false;
}

int prime(int n)
{int i=n-1;int j;
if(n>1) {j=prime(n-1)+1;
	
	while(i>0)	{if(coprime(prime(i),j)==true)
				{if(i==1) return j; else i--;}
			else {i=n-1;j++;}
			}
	}

else return 2;
 	
}

int main()
{int n;
cout<<"n="<<endl; cin>>n;
if(primeness(n)==true) cout<<"prime"<<endl;

return 0;

}

The following program responds correctly for n=1318699, which is prime and n=1318690, which is not; but it tells that 111111111112 is prime, which the number is not! Why is the problem?

#include<iostream>
#include<cmath>

using namespace std;

bool primeness(int m)
{int i=2;float k,y;int j;
y=m;
bool pr=true;
while(i<=m/2)
{k=y/i;j=m/i;
if(j==k) pr= false;
i++;}
return (pr);
}

int main()
{int n;
cout<<"n="<<endl; cin>>n;
if(primeness(n)==true) cout<<"prime"<<endl;

return 0;

}

Thanks,
Saurav

[WingedPanther]

First issue: your code is hard to read, because of the formatting.
Second issue: you are comparing floats, which is fairly dangerous, instead of using modulo division to test divisibility.

Originally Posted by saurav

Hello,
I am trying to develop a c++ program that would, given any integer, decide whether it is prime. My program responds for small numbers, but doesn't if the number is great enough!

Consider this code, which is very basic, and which responds for n=11117, but falls through (hangs) for 111127

#include<iostream>
#include<cmath>
using namespace std;
bool divisibility(int i,int j)  //this function is unnecessary.  Use modular division
{float k; k=float(j);
if(i==0) return false; 
else if(j/i ==k/i) return true;
else return false;}

int gcd(int i,int j)
{ 
if(divisibility(i,j)==true) return i;
else if(divisibility(j,i)==true) return j;
else if(i==1||j==1) return 1;
else    {
	int k,l; if(j<i) k=j;else k=i;
	
	if(k>0)
		{while(k>0)
		{if(divisibility(k,i)==true&&divisibility(k,j)==true) return k;
		else k--;}				
		}
	else return 1;
	}
}




bool coprime(int i,int j)
{if(gcd(i,j)==1) return true;
else return false;}



bool primeness(int n)  //see below for example of clearer indenting
{
  int i;
  if(n>1)
  {
    int i=1;   
    if((i-1)<n/2)
    {
      while((i-1)<=n/2)
      {
        if(coprime(i,n)==true)
        {
          if((i-1)==n/2) return true;
          else i++;
        }
        else return false;
      }
    }
  }
  else return false;
}

int prime(int n)
{int i=n-1;int j;
if(n>1) {j=prime(n-1)+1;
	
	while(i>0)	{if(coprime(prime(i),j)==true)  //why check coprime?  you will run into a divisor before a non-divisor non-coprime number?
				{if(i==1) return j; else i--;}
			else {i=n-1;j++;}
			}
	}

else return 2;
 	
}

int main()
{int n;
cout<<"n="<<endl; cin>>n;
if(primeness(n)==true) cout<<"prime"<<endl;

return 0;

}

The following program responds correctly for n=1318699, which is prime and n=1318690, which is not; but it tells that 111111111112 is prime, which the number is not! Why is the problem?

#include<iostream>
#include<cmath>

using namespace std;

bool primeness(int m)
{
  int i=2;
  float k,y;
  int j;
  y=m;
  bool pr=true;
  while(i<=m/2)
  {
    k=y/i;
    j=m/i;
    f(j==k) pr= false;
    i++;
  }
  return (pr);
}

int main()
{int n;
cout<<"n="<<endl; cin>>n;
if(primeness(n)==true) cout<<"prime"<<endl;

return 0;

}

Thanks,
Saurav

[kkelly]

I definitely wouldn't use floats, and I wouldn't even use ints. Use unsigned ints. Understanding how numbers are handled by the processor is very important if not paramount. There are more than a few standards, and I'm sorry I don't have any links. You might want to google "Floating Point representation", or "numeric representation". Given your ouput, I'm guessing you problems are stemming from truncation, and/or floating point inprecision.
I didn't look through your code, but unless you are implementing an advanced algorithm, searching for primes is a simple matter.

unsigned int uintNum;			//	The number to test
unsigned int uintMod;			//	The modulus.

bool blIsPrime;				//       Prime? Yes or No
blIsPrime = true;				//	We'll assume it yes, and try to prove it otherwise

uintMod = 2;				//	We'll start at modulo 2 since it is our first potential factor

//	If our modulus is more than half our number we can stop testing.
//	So, while the number may be prime and the modulus is less than half
while ((blIsPrime) && (uintMod <= (uintNum/2)))
{
	//	if the number is in the modulus set it can't be prime
	if (uintNum%uintMod == 0)
	{
		blIsPrime = false;
	}
	else
	{
		//	increment modulus
		uintMod++;
	}
}

[Patrick]

Anybody got it running here. Whenever I try to decompile it I got some error like blinking of a black window and getting no output. I am using Borland C++ V6.

Any ideas please.

[kkelly]

The above code has no input nor output mechanism. It is just the algorithm. Here a copy that you can copy and paste.

#include <iostream>

using namespace std;

int main()
{

	unsigned int uintNum;			//	The number to test
	unsigned int uintMod;			//	The modulus.

	bool blIsPrime;				//       Prime? Yes or No
	blIsPrime = true;				//	We'll assume it is prime, and try to prove otherwise

	uintMod = 2;				//	We'll start at modulo 2 since it is our first potential factor

	cout << "Enter Number: ";
	cin >> uintNum;
	cin.get();
	//	If our modulus is more than half our number we can stop testing.
	//	So, while the number may be prime and the modulus is less than half
	while ((blIsPrime) && (uintMod <= (uintNum/2)))
	{
		//	if the number is in the modulus set it can't be prime
		if (uintNum%uintMod == 0)
		{
			blIsPrime = false;
		}
		else
		{
		//	increment modulus
			uintMod++;
		}
	}

	if (blIsPrime)
	{
		cout << uintNum << " is prime.";
	}
	else
	{
		cout << uintNum << " is not prime.";
	}

	cin.get();
	return 0;
}

Remember that the range of an unsigned integer, given that it is 4 bytes, is 0 - 4294967295.