+ Reply to Thread
Results 1 to 5 of 5

Thread: problem with large numbers

  1. #1
    Newbie saurav is an unknown quantity at this point
    Join Date
    Aug 2007
    Posts
    8

    problem with large numbers

    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

    Code:
    #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?

    Code:
    #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

  2. #2
    Super Moderator WingedPanther has much to be proud of WingedPanther has much to be proud of WingedPanther has much to be proud of WingedPanther has much to be proud of WingedPanther has much to be proud of WingedPanther has much to be proud of WingedPanther has much to be proud of WingedPanther has much to be proud of WingedPanther has much to be proud of WingedPanther's Avatar
    Join Date
    Jul 2006
    Age
    36
    Posts
    11,648
    Blog Entries
    57
    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.

    Quote Originally Posted by saurav View Post
    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

    Code:
    #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?

    Code:
    #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
    CodeCall Blog | CodeCall Wiki | Shareware
    Programming is a branch of mathematics.
    My CodeCall Blog | My Personal Blog

  3. #3
    Learning Programmer kkelly is an unknown quantity at this point kkelly's Avatar
    Join Date
    Sep 2007
    Posts
    50
    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.
    Code:
    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++;
    	}
    }

  4. #4
    Programmer Patrick is an unknown quantity at this point
    Join Date
    Sep 2007
    Posts
    100
    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.

  5. #5
    Learning Programmer kkelly is an unknown quantity at this point kkelly's Avatar
    Join Date
    Sep 2007
    Posts
    50
    The above code has no input nor output mechanism. It is just the algorithm. Here a copy that you can copy and paste.
    Code:
    #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.

+ Reply to Thread

Thread Information

Users Browsing this Thread

There are currently 1 users browsing this thread. (0 members and 1 guests)

     

Similar Threads

  1. i have a problem please help me!!!????
    By stack in forum Java Help
    Replies: 10
    Last Post: 05-26-2009, 08:35 AM
  2. Peculiar UI Problem Needs Tackling
    By adriyel in forum C# Programming
    Replies: 2
    Last Post: 04-06-2008, 07:46 AM
  3. [C] Comparison problem
    By Alhazred in forum C and C++
    Replies: 1
    Last Post: 08-29-2007, 04:58 AM
  4. Large powers
    By tim1234 in forum C and C++
    Replies: 5
    Last Post: 12-29-2006, 11:29 AM
  5. A small problem in the output
    By The_Master in forum C and C++
    Replies: 3
    Last Post: 12-13-2006, 12:04 PM

Bookmarks

Bookmarks

     
        Algorithms and Data Structures

        Java tutorials

        Algorithms Forum

Posting Permissions

  • You may not post new threads
  • You may not post replies
  • You may not post attachments
  • You may not edit your posts