# Homework Help: C: Highly prime numbers

Tags:
1. Feb 29, 2016

### gruba

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

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

return 0;
}

Last edited: Feb 29, 2016
2. Feb 29, 2016

### Samy_A

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

3. Feb 29, 2016

### BvU

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

 quick work Samy !

4. Feb 29, 2016

### gruba

[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);

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

return 0;
}

Last edited: Feb 29, 2016
5. Feb 29, 2016

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

Last edited: Feb 29, 2016
6. Feb 29, 2016

### gruba

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

7. Feb 29, 2016

### Samy_A

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
8. Feb 29, 2016

### gruba

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

9. Feb 29, 2016

### Samy_A

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.