How to determine primes in part of a program

[jgkhawks]

Hey, so far i have compiled most of the program i need, but I'm stuck with how to determine whether some part of an input is prime. THis is what I have so far

#include <stdio.h>
int main(void) {

int pass=0;

int Pdig1=0;
int Pdig2=0;
int Pdig3=0;
int Pdig4=0;
int Pdig5=0;
int Pdig6=0;
int Pdig7=0;
int Pdig8=0;

int num1=0;
int num2=0;
int num3=0;
int num4=0;
int num5=0;
int num6=0;
int num7=0;

int counter=0;


printf("Enter a password between 5 and 8 digits.\n");
scanf("%d",&pass);

while(pass){
pass=pass/10;
counter++;
}
(Pdig1=pass/10000000);
(num1=pass%10000000);

(Pdig2=num1/1000000);
(num2=num1%1000000);

(Pdig3=num2/100000);
(num3=num2%100000);

(Pdig4=num3/10000);
(num4=num3%10000);

(Pdig5=num4/1000);
(num5=num4%1000);

(Pdig6=num5/100);
(num6=num5%100);

(Pdig7=num6/10);
(num7=num6%10);



if(!((counter<=8)&&(counter>=5))){
printf("Password is invalid, must be between 5 and 8 digits.\n");
}else{
if((Pdig7==Pdig3)&&(Pdig6==Pdig4)){
//I need to do the prime number check here
}else{
printf("Password is invalid, last 5 digits must be a palindrome.\n");
}
}


return 0;
}



The guidelines are

1. The password must be between 5 and 8 digits long (assume no leading zeros are entered – for example: 002345 is considered only 4 digits for our purposes).
2. The last five digits of the password must be a palindrome (i.e. the same backwards as it is forwards, such as 52425).
3. The last three digits of the password must be a prime number (i.e. if the password entered was 730103, 103 is prime).


Thanks for any help you guys can provide.

[K0T4K0t4]

are you only having problems determining if the last 3 digits of a number are prime?
if thats the case look at http://en.wikipedia.org/wiki/Primality_test

[AbstractionAnon]

What exactly are you having trouble with?

[jgkhawks]

Figuring out a method to test the primality of the last three digits of an inputted number

[Chervil]

The code so far has several bugs:

1.The loop while(pass){ ensures that the value of pass is zero after the completion of the loop. Thus all subsequent processing is moot.

2. No value (other than initial zero) is assigned to Pdig8.

3. The palindrome test should operate on digits Pdig4 through Pdig8.

Now moving on to the primality test. The individual digits can be re-assembled into a three digit number like this:

    int testnum = Pdig6 * 100 + Pdig7 * 10 + Pdig8;

After that, the value testnum can be tested as to whether it is prime. It's probably easiest to use a separate function to carry out this task.
(edit: num5 also consists of the last three digits)

The topic of testing to see whether a number is prime or not crops up regularly on these forums, there are lots of previous examples to borrow from.

[jgkhawks]

1. Will changing while(pass) to while(pass>0) fix that issue

2. And shouldn't Pdig8 be where num7 is on the last line of determining the digits part of the code

3. Instead of using that code is there a way to say if "num3 equals the reverse of num3, then its palindrome"( num3 becuase it is the number that contains 5 digits)

Thanks for pointing out these issues btw.

[AbstractionAnon]

1) No. The point was that inside your while loop, you repeatedly divide pass by 10. You don't exit the loop until psss is equal to zero. The subsequent statements calculating pdig1 thru num7 are all operating on a value of zero.

2. Yes.

3. Chervil's point was that you had the right idea with your palindrome check, but were checking the wrong digits. It should have been:

if ((Pdig4==Pdig8) && (Pdig5==Pdig7))

PLEASE USE CODE TAGS (the <> formatting button) when posting code. It allows us to refer to specific lines in your code.

[Chervil]

1. Will changing while(pass) to while(pass>0) fix that issue

No. The simplest solution is to keep a copy of the password in another variable.

2. And shouldn't Pdig8 be where num7 is on the last line of determining the digits part of the code

Not sure, but I think the answer is in the code I share below.

3. Instead of using that code is there a way to say if "num3 equals the reverse of num3, then its palindrome"( num3 becuase it is the number that contains 5 digits)

That may be possible, but when you already have the number dissected into individual digits I'd keep the existing technique.

Here's part of the code which I tried:

    int copypass = pass;
    while (copypass) {
        copypass=copypass/10;
        counter++;
    }

    Pdig1 = pass/10000000;
    num1  = pass%10000000;

    Pdig2 = num1/1000000;
    num2  = num1%1000000;

    Pdig3 = num2/100000;
    num3  = num2%100000;

    Pdig4 = num3/10000;
    num4  = num3%10000;

    Pdig5 = num4/1000;
    num5  = num4%1000;

    Pdig6 = num5/100;
    num6  = num5%100;

    Pdig7 = num6/10;
    num7  = num6%10;

    Pdig8 = num7/1;

Notice line 28 Pdig8 = num7/1; of course division by 1 is not necessary, but it means the code retains a sense of symmetry, and often in programming that can be a good guide to correctness.

One thing which seemed likely, was that some of this code was done without actually testing it. What I tend to do during development is put lots of extra printf or cout statements to display values at various stages in the code, to allow me to see whether the code is working as expected. Certainly when I first tried the code originally posted above, I saw got zero in every digit and pretty soon realised that some things were not quite right.

So I do recommend extra printf statements for debugging, remove them when everything is working. An example:

    printf("%d  %d  %d  %d  %d  %d  %d  %d  \n",
           Pdig1,Pdig2,Pdig3,Pdig4,Pdig5,Pdig6,Pdig7,Pdig8);

[jgkhawks]

Ok thanks that makes much more sense, I got the last two parts. Back to the first though, should i move that while loop to right before my if statments?
like this

    (Pdig1=pass/10000000);
    (num1=pass%10000000);

    (Pdig2=num1/1000000);
    (num2=num1%1000000);

    (Pdig3=num2/100000);
    (num3=num2%100000);

    (Pdig4=num3/10000);
    (num4=num3%10000);

    (Pdig5=num4/1000);
    (num5=num4%1000);

    (Pdig6=num5/100);
    (num6=num5%100);

    (Pdig7=num6/10);
    (num7=num6%10);

    (Pdig8=num7/1);
    
     while(pass){
      pass=pass/10;
      counter++;
  }

  if(!((counter<=8)&&(counter>=5))){
    printf("Password is invalid, must be between 5 and 8 digits.\n");
  }else{
if((Pdig8==Pdig4)&&(Pdig7==Pdig5)){
                                                   //I need to do the prime number check here
    }else{
        printf("Password is invalid, last 5 digits must be a palindrome.\n");
    }
  }


  return 0;
}

And sorry I knew there was a way but wasn't sure on how to use code tags.

Edit: ya thanks that copy of the password is a lot easier to use.

[jgkhawks]

This is my updated code

#include <stdio.h>
int main(void) {

    int pass=0;

    int Pdig1=0;
    int Pdig2=0;
    int Pdig3=0;
    int Pdig4=0;
    int Pdig5=0;
    int Pdig6=0;
    int Pdig7=0;
    int Pdig8=0;

    int num1=0;
    int num2=0;
    int num3=0;
    int num4=0;
    int num5=0;
    int num6=0;
    int num7=0;

    int counter=0;


    printf("Enter a password between 5 and 8 digits.\n");
    scanf("%d",&pass);

    int copypass = pass;
    while (copypass) {
        copypass=copypass/10;
        counter++;

    }


    (Pdig1=pass/10000000);
    (num1=pass%10000000);

    (Pdig2=num1/1000000);
    (num2=num1%1000000);

    (Pdig3=num2/100000);
    (num3=num2%100000);

    (Pdig4=num3/10000);
    (num4=num3%10000);

    (Pdig5=num4/1000);
    (num5=num4%1000);

    (Pdig6=num5/100);
    (num6=num5%100);

    (Pdig7=num6/10);
    (num7=num6%10);

    (Pdig8=num7/1);


  if(!((counter<=8)&&(counter>=5))){
    printf("Password is invalid, must be between 5 and 8 digits.\n");
  }else{
  if((Pdig8==Pdig4)&&(Pdig7==Pdig5)){
    int testnum = Pdig6 * 100 + Pdig7 * 10 + Pdig8;
    if(testnum ){                                               //if its prime
        printf("Password Accepted. The password you have entered can be used\n to encript and protect data.");
    }else{
        printf("Password is invalid, last 3 digits must be a prime number.\n");
    }
    }else{
        printf("Password is invalid, last 5 digits must be a palindrome.\n");
    }
  }

  printf("%d  %d  %d  %d  %d  %d  %d  %d  \n",
           Pdig1,Pdig2,Pdig3,Pdig4,Pdig5,Pdig6,Pdig7,Pdig8);



  return 0;
}

I everything seems to be working, i'm just stuck on the prime number check now. The wikipedia page was somewhat helpful but i got confused when they show wilson's theorem and proceed to say it is invalid

[jgkhawks]

Also i have only 45 minutes or so (yes i know thats my fault), so a quick response would be appreciated but thanks a lot for what you guys have helped with so far.

[RobertEagle]

If you want to find out the if it's a prime number you can also do it in 2 ways.

1. Trough looping. Let's imagine you are passing to a function the number to be found out, and returns 1 if is prime or 0 if it isn't. Check my example:

bool isPrimeFor(int num)
{
	if(num==1)
	{
		return 1;
	}
	bool counter=0;
	for(int i=2; i<=num; i++) 
	{
		if(num%i==0 && i<num)
		{
			return 0;
		}
	}
	return 1;
}

2. Trough recursion. It costs you more resources but it's much easy to understand if your program tends to be big. The num is the number to be verified, and i is the iterator which must start from 1. So you call this function in this way: isPrimeRec(mynumber,1)

bool isPrimeRec(int num,int i)
{
	if(i<num)
	{
		if(num%i==0 && i!=1)
		{
			return 0;
		}
		else
		{
			return isPrimeRec(num,i+1);
		}
	}
	return 1;
}

Hope I helped you,
RobertEagle

EDIT: Think about the 2 properties prime number has. Grab a pen a think firstly on the paper, than in the program. Don't try to ,,copy" the formulas.

[Chervil]

Scroll to the top of this page, you will see a search box. Put "prime number" in that box and click go. You will find lots of previous threads on this forum

[Smac89]

#include <cstdlib>
#include <cstdio>
#include <math.h>

using namespace std;

typedef unsigned int uint;

long pows_n(long val, int exp)
{
    if (exp == 0)
        return 1;
    return val * pows_n(val, --exp);
}

bool isPrime(int Val)
{
    int B = sqrt(Val);
    for (int r = 2; r <= B; ++r)
    {
        if (Val % r == 0)
        {
            return false;
            break;
        }
    }
    return true;
}


bool isPal(int num, int size)
{
    if (size == 0)
        return true;
    
    uint hg = pows_n(10, size);
    int tr = num % 10;
    int sr = num/hg;
    
    if (tr != sr)
        return false;
    
    num -= sr * hg;
    num /= 10;
    size -= 2;
    
    return isPal(num, size);
}

int main()
{
    int pass;
    int length = 0;
    
    do
    {
        puts("Enter a password between 5 and 8 digits: ");
        scanf("%d", &pass);
        length = log10(pass) + 1;
        
    } while (length < 5 || length > 8);
    
    int temp = pass;
    int lemp = length - 1;
    
    while(lemp >= 3)
    {
        uint v = pows_n(10, lemp);
        int s = temp / v;
        if (lemp == 4)
            if (temp % 10 != 0)//Palindromes are not evenly divisible by 10
            {
                if (!isPal(temp, lemp))
                {
                    puts ("Invalid Password, last 5 digits are not palindrome\n");
                    return 0;
                    break;
                }
            }
            else
            {
                puts ("Invalid Password, last 5 digits are not palindrome\n");
                return 0;
                break;
            }
        lemp--;
        temp -= s * v;
    }
    
    if (isPrime(temp))
        puts("The password is valid\n");
    else
        puts("The password is invalid\n");
    
    return 0;
}

[RobertEagle]

Smac89, one question I have, if you allow me:

Why use the recursion when the algorithms are easy solvable with for/while loops?

Thank you,
RobertEagle

[AbstractionAnon]

@smac89 - Line 71, you're saying plaindromes are not evenly divisible by 10.

Wouldn't the last 5 digits of a password being "01210" be a palindrome that is evenly divisible by 10?

[Smac89]

@AbstractionAnon
As soon as 01210 is read as an integer, it is translated to 1210 which is not palindrome. Also generally, no palindrome number is divisible by 10

@RobertEagle
I had done something similar with strings and I had used recursion; so I just translated everything to work for numbers but kept the recursiveness

[AbstractionAnon]

@smac89 - The original requirement was that the password was 5 to 8 digits in length. If the password is longer than 5 digits, then the leading zero in 01210 is clearly significant as the last five digits are indeed a palindrome. Consider 901210, which meets all of the original requirements, but fails your divide by 10 test.

Since the OP's code entered the password as an integer, we have no way to know if exactly 5 digits with a leading zero was entered or not. Had the password been entered as character data, then we could determine if a leading zero had been entered or not.

The OP's code does disallow both 1210 and 01210 since his count loop at line 30 (and your log() calculation) would determine either password has a length of 4. The original requirements do not state if leading zeroes entered by the used should be considered as significant or not.

edit: Struck reference to 901210 has meeting the original requirements. It fails test #3 for primality.

My point still is why special case divisibility by 10 at line 71. The test for primality will catch this. If you're going to spcial case divisibility by 10, why not also special case passwords ending in 2,4,6, and 8?