1. Limited time only! Sign up for a free 30min personal tutor trial with Chegg Tutors
    Dismiss Notice
Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

C: Highly prime numbers

  1. Feb 29, 2016 #1
    1. The problem statement, all variables and given/known data
    Write a program that will print all highly prime numbers from the input interval <a,b>. Prime number is highly prime if deletion of every digit from right is a prime.

    Example:
    239 is highly prime because 239,23,2 are primes.

    2. The attempt at a solution
    Could someone point out what are logic errors in the following program:
    Code (Text):

    #include <stdio.h>

    int isPrime(int p);
    int isHighlyPrime(int n);
    void printHighlyPrimeNumbers(int a,int b);

    // check if p is a prime
    int isPrime(int p)
    {
      int nd=2;//number of divisors
      int d;//current divisor

      for(d=2; d<p/2; d++)
      {
      if(p % d == 0)
      nd++;
      }
      if(nd == 2)
      return 1;
      return 0;
    }

    // check if n is highly prime
    int isHighlyPrime(int n)
    {
      int temp=n;
      int i;
      int digitCount=0;//number of digits in n

      while(temp != 0)
      {
      temp=temp/10;
      digitCount++;
      }
      temp=n;

      //if number of digits is 1, only check if prime
      if(digitCount == 1)
      {
      if(isPrime(temp))
      return 1;
      }

      //else check if n,n/10,(n/10)/10,... are primes
      else
      {
      for(i=1; i<=digitCount-1 && isPrime(temp); i++)
      {
      if(isPrime(temp))
      temp=temp/10;
      }
      return 1;
      }
      return 0;
    }

    //print highly primes from a to b
    void printHighlyPrimeNumbers(int a,int b)
    {
      int i;
      for(i=a; i<=b; i++)
      {
      if(isHighlyPrime(i))
      printf("%d ",i);
      }
    }

    int main()
    {
      int a,b;
      do
      {
      printf("a = ");
      scanf("%d",&a);
      }while(a<1);
      do
      {
      printf("b = ");
      scanf("%d",&b);
      }while(b<1);
     
      //swap if a>b
      if(a > b)
      {
      int temp=a;
      a=b;
      b=temp;
      }

      printHighlyPrimeNumbers(a,b);

      return 0;
    }
     
     
    Last edited: Feb 29, 2016
  2. jcsd
  3. Feb 29, 2016 #2

    Samy_A

    User Avatar
    Science Advisor
    Homework Helper

    This part I don't get:
    Code (C):
    for(i=1; i<=digitCount-1 && isPrime(temp); i++)
      {
      if(isPrime(temp))
      temp=temp/10;
      }
    I would keep the for loop simple:
    Code (C):
    for(i=1; i<=digitCount-1; i++)
     
    Then, if isPrime(temp) returns 0, isHighlyPrime should immediately return 0.

    (Also, note that your isPrime function considers 4 a prime number.)
     
  4. Feb 29, 2016 #3

    BvU

    User Avatar
    Science Advisor
    Homework Helper
    Gold Member

    Seems flawed: if it's prime you don't have to IF again. If it's not prime, you should not return 1 .

    [edit] quick work Samy !
     
  5. Feb 29, 2016 #4
    [EDIT]I have figured out the problem, here is the working program:
    Code (Text):

    #include <stdio.h>

    int isPrime(int p);
    int isHighlyPrime(int n);
    void printHighlyPrimeNumbers(int a,int b);

    // check if p is a prime
    int isPrime(int p)
    {
      int i = 2;
     if(p == 1 || p == 7)
        return 0;
      while(i<p){
      if(!(p % i)) return 0;
      i = 2*i-1;
      }
      return 1;
    }

    // check if n is highly prime
    int isHighlyPrime(int n)
    {
      int temp=n;
      int i;
      int digitCount=0;//number of digits in n

      while(temp != 0)
      {
      temp=temp/10;
      digitCount++;
      }
      temp=n;

      //if number of digits is 1, only check if prime
      if(digitCount == 1)
      {
      if(isPrime(temp))
      return 1;
      }

      //else check if n,n/10,(n/10)/10,... are primes
      else
      {
      while(temp>0)
      {
      if(isPrime(temp) == 0)
      {
      return 0;
      }
      temp =temp/10;
      }
      return 1;
      }
      return 0;
    }

    //print highly primes from a to b
    void printHighlyPrimeNumbers(int a,int b)
    {
      int i;
      for(i=a; i<=b; i++)
      {
      if(isHighlyPrime(i))
      printf("%d ",i);
      }
    }

    int main()
    {
      int a,b;
      do
      {
      printf("a = ");
      scanf("%d",&a);
      }while(a<1);
      do
      {
      printf("b = ");
      scanf("%d",&b);
      }while(b<1);

      //swap if a>b
      if(a > b)
      {
      int temp=a;
      a=b;
      b=temp;
      }

      printHighlyPrimeNumbers(a,b);

      return 0;
    }
     
     
    Last edited: Feb 29, 2016
  6. Feb 29, 2016 #5

    Samy_A

    User Avatar
    Science Advisor
    Homework Helper

    Some examples: the program treats numbers as 113, 131, 137 ... as highly prime.
    Also 77, 371, 377 and 1133, which are not prime.

    Something still wrong with the isPrime function.
     
    Last edited: Feb 29, 2016
  7. Feb 29, 2016 #6
    I have edit the previous post, but not sure if it will correct possible error.
     
  8. Feb 29, 2016 #7

    Samy_A

    User Avatar
    Science Advisor
    Homework Helper

    Still gives 371 and 373 as primes (as examples).
    As 7 is prime, returning 0 when p==7 doesn't make much sense.

    The key issue is this: in isPrime, you check if p is divisible by i=2, and then by i=2*2-1=3, i=2*3-1=5, i=2*5-1=9, ...
    See the problem?
     
    Last edited: Feb 29, 2016
  9. Feb 29, 2016 #8
    The following isPrime() function seems to work for interval 50 - 1200:
    Code (Text):

    int isPrime(int p)
    {
      int i;
      if(p == 1)
      return 0;
      for(i=2; i<=p/2; i++)
      if(p % i == 0)
      return 0;
      return 1;
    }
     
     
  10. Feb 29, 2016 #9

    Samy_A

    User Avatar
    Science Advisor
    Homework Helper

    Yes, this one looks ok (I'm tired, so I may miss something). There is room for improvement as far as performance is concerned, but probably that is not important at this stage.
     
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook

Have something to add?
Draft saved Draft deleted



Similar Discussions: C: Highly prime numbers
  1. Determine prime number (Replies: 8)

Loading...