Question

Many types of identification numbers, including credit card numbers, must satisfy the Luhn Algorithm in order to be considered "valid". This algorithm verifies the number by performing the following operation: starting from the right-most digit, double every 2nd digit. If this doubling causes that digit to be greater than 9, subtract 9 from it. Now add up all the new digits of the number (including the digits that weren't doubled). If the sum is evenly divisible by 10, then the number is valid, otherwise it is not. For example, for the number 2395129857 this would be:

2 3 9 5 1 2 9 8 5 7

2x2 3 9x2 5 1x2 2 9x2 8 5x2 7 (doubling every 2nd digit from right)

4 3 18 5 2 2 18 8 10 7

4 3 9 5 2 2 9 8 1 7 (subtract 9 from any digit greater than 9)

4 + 3 + 9 + 5 + 2 + 2 + 9 + 8 + 1 + 7 = 50

Since 50 is divisible by 10, this number satisfies the Luhn criteria, and is therefore valid.

a) Write a C function called check_luhn that takes a single integer as input, and returns 1 if the number is valid according to the Luhn algorithm, or 0 if not. HINT: Start from the right-most digit, and use simple C operators to find both the digit and the remaining number once that digit is removed. Then process that number if necessary and add it to the sum.

b) Using the function written in part (a), write a C program to print all of the "valid" numbers between 10000000 and 99999999

c) Please provide a short description (in bullet points) of an explanation of how the program works

Answer 1

// C program to display all the valid numbers between 10000000 and 99999999 using luhn algorithm

#include <stdio.h>
#include <stdlib.h>

// function declaration
int check_luhn(int number);

int main()
{
// set start counter to 10000000
int start = 10000000;
printf("Valid Numbers between 10000000 and 99999999:\n");

// loop from 10000000 to 99999999(inclusive)
while(start <= 99999999)
{
// if start is a valid number, display the number
if(check_luhn(start))
printf("\n%d",start);
start += 1; // increment start by 1
}

return 0;
}

// function to return 1 if number is valid else return 0
int check_luhn(int number)
{
int lastDigit = number%10; // get the last digit of the number and store it in lastDigit
number = number/10; // get the number after removing the last digit

// initialize sum to 0
int sum = 0, digit;
int isEven = 1; // set isEven to 1 (to determine if the digit is even or not starting with the second last)

// loop that continues till number > 0
while(number > 0)
{
digit = number%10; // get the last digit of the number
number /= 10; // remove the last digit from the number
if(isEven) // check if this is an even digit
{
isEven = 0; // negate isEven
digit *= 2; // double the digit
if(digit > 9) // if digit > 9, subtract 9 from digit
digit -= 9;
}else // not an even digit, negate isEven
isEven = 1;

sum += digit; // add digit to sum
}

// if sum +lastDigit is divisible by 10, it is a valid number
if((sum+lastDigit)%10 == 0)
return 1;
else // not a valid number
return 0;
}

//end of program

Output: (Some of the numbers)