Print Highly Prime Numbers in an Input Interval | C Program

[gruba]

Homework Statement

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:

#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;
}

 

[Samy_A]

Homework Statement

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:

#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;
}

This part I don't get:

for(i=1; i<=digitCount-1 && isPrime(temp); i++)
  {
  if(isPrime(temp))
  temp=temp/10;
  }

I would keep the for loop simple:

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.)

 

[BvU]

else
  {
  for(i=1; i<=digitCount-1 && isPrime(temp); i++)
  {
  if(isPrime(temp))
  temp=temp/10;
  }
  return 1;
  }
  return 0;
}

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 !

 

[gruba]

[EDIT]I have figured out the problem, here is the working program:

#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;
}

 

[Samy_A]

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.

 

[gruba]

Something still wrong with the isPrime function.

I have edit the previous post, but not sure if it will correct possible error.

 

[Samy_A]

I have edit the previous post, but not sure if it will correct possible error.

[EDIT]I have figured out the problem, here is the working program:

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;
}

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?

 

[gruba]

Still gives 371 and 373 as primes (as examples).
As 7 is prime, returning 0 when p==7 doesn't make much sense.
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?

The following isPrime() function seems to work for interval 50 - 1200:

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;
}

 

[Samy_A]

The following isPrime() function seems to work for interval 50 - 1200:

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;
}

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.