Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

C++ programming on prime numbers

  1. Feb 18, 2014 #1
    this is the program which i wrote:

    #include<iostream.h>
    #include<conio.h>
    #include<stdlib.h>
    void prime(int p)
    {
    if(p==0||p==1)
    {
    cout<<"neither prime nor composite"<<endl;
    getch();
    exit(1);
    }
    for(int i=2;i<p/2;i++)
    {
    if(p%i==0)
    {
    cout<<"composite"<<endl;
    break;
    }
    else
    cout<<"prime"<<endl;
    }
    }
    void main()
    {
    int n;
    clrscr();
    cout<<"enter a number:"<<endl;
    cin>>n;
    prime(n);
    getch();
    }


    it is not working for some numbers like 9,5,2,etc..

    if i input 9
    output is :

    composite
    prime

    if i input 5
    nothing is displayed


    i debugged and no errors came
    what exactly is wrong with this code?
     
  2. jcsd
  3. Feb 18, 2014 #2
    That output looks right for that code. Let's look at your two cases to see what the program actually does.

    If p=9, p/2=4 (remember integer division). Due to the test in the for loop, you will test the values i=2 and i=3. In the case of i=2, 9%2=1 and it prints prime no matter what the later tests will give. For i=3, 9%3=0 and it prints composite. You probably don't want to print prime until you've verified that no numbers covered in the loop are factors of p.

    If p=5, p/2=2. This means that the for loop won't run at all, since 2 isn't less than 2. You probably do want to run the loop at least once.
     
  4. Feb 18, 2014 #3
    #include<iostream.h>
    #include<conio.h>
    #include<stdlib.h>
    void prime(int p)
    {
    int count=1;
    if(p==0||p==1)
    {
    cout<<"neither prime nor composite"<<endl;
    getch();
    exit(1);
    }
    for(int i=2;i<=p/2;i++)
    {
    if(p%i==0)
    count++;
    }
    if(count>=2)
    cout<<"not a PRIME NUMBER"<<endl;
    else
    cout<<"PRIME NUMBER"<<endl;
    }
    void main()
    {
    int n;
    clrscr();
    cout<<"enter a number:"<<endl;
    cin>>n;
    prime(n);
    getch();
    }


    now is it correct?
    o:)
     
  5. Feb 18, 2014 #4

    Borek

    User Avatar

    Staff: Mentor

    Use [noparse]
    Code (Text):
     
    [/noparse] tags:

    Code (Text):
    #include<iostream.h>
    #include<conio.h>
    #include<stdlib.h>

    void prime(int p)
    {
       int count=1;

       if(p==0||p==1)
       {
          cout<<"neither prime nor composite"<<endl;
          getch();
          exit(1);
       }
       for(int i=2;i<=p/2;i++)
       {
          if (p%i==0)
             count++;
       }
       if(count>=2)
          cout<<"not a PRIME NUMBER"<<endl;
       else
          cout<<"PRIME NUMBER"<<endl;
    }

    void main()
    {
       int n;

       clrscr();
       cout<<"enter a number:"<<endl;
       cin>>n;
       prime(n);
       getch();
    }
    For the code readability, correct formatting is paramount.
     
  6. Feb 18, 2014 #5

    D H

    User Avatar
    Staff Emeritus
    Science Advisor

    Strictly speaking, it's not correct. All it takes is one number to divide p with zero remainder and p is not prime. Your program will happen to have at least two divisors, but that's because your loop go to and including p/2. There's no reason to do that. Once you find one such divisor you know the number cannot be prime. Exit the loop immediately. There's no reason to go all the way to p/2. You only need to go up to and including sqrt(p). While the difference between p/2 and sqrt(p) is small for small numbers, it's not small at all for bit numbers. For example, a limit of p/2 means checking 500,000,000,019 numbers in the case p=1,000,000,000,039. A limit of sqrt(p) means you only need to check 1,000,000 numbers to see that 1,000,000,000,039 is indeed a prime. (And you can reduce this by a factor of two if you check 2 and then only check odd numbers).
     
  7. Feb 18, 2014 #6
    anyways for small numbers<100 i am getting correct results

    and for bit numbers as you said for 1,000,000,000,039 i have to use longint instead of int
     
  8. Feb 18, 2014 #7

    D H

    User Avatar
    Staff Emeritus
    Science Advisor

    The same argument applies to 2147483647 (which does fit within an int). Try this number. Your program takes an inordinate amount of time to say that this is a prime number. That is not acceptable. Ending your loop at 46340 rather than 1073741823 (in this case) would make your program 23,000 times faster.

    BTW, you need to get a better compiler. Given your include files and your arcane use of void main, I suspect you are using Turbo C++. You should get a compiler that was written in this millennium. There are plenty of free compilers around. There is *no* reason to use Turbo C++ anymore.
     
    Last edited: Feb 18, 2014
  9. Feb 18, 2014 #8
    it is a prime number

    if my program is too slow i can make use of INLINE function.
     
  10. Feb 18, 2014 #9

    Borek

    User Avatar

    Staff: Mentor

    It won't change much.

    The fastest operation is the one never performed. D H told you how to implement it in your case, but apparently your prefer to not listen to the good advice.
     
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook




Similar Discussions: C++ programming on prime numbers
  1. C program-prime (Replies: 6)

  2. C programming (Replies: 9)

Loading...