In this course, we will cover coding test problems using C#.
The topic is “Finding the minimum value among prime and palindrome numbers within a given range.”
This problem emphasizes algorithmic thinking and allows you to learn various approaches to writing efficient code.
Problem Description
Given an integer N,
the task is to find all prime and palindrome numbers among the integers from 1 to N and determine the minimum value among them.
A prime number is a positive integer greater than 1 that has no positive divisors other than 1 and itself,
and a palindrome number is a number that reads the same forward and backward.
Input
– Integer N (1 ≤ N ≤ 1,000,000)
Output
– Print the minimum value among the prime and palindrome numbers.
– If there are no such numbers, you should print -1.
Example Input
31
Example Output
11
Algorithm Analysis
To solve this problem, we can approach it in the following steps:
- Prime Check: Implement an algorithm to check if numbers within the given range are prime.
- Palindrome Check: Write a function to check if each number is a palindrome.
- Finding Minimum: Collect the numbers that are both prime and palindrome, then return the minimum value.
C# Code Implementation
Below is the code to solve the problem using C#.
using System;
using System.Collections.Generic;
class Program
{
static void Main()
{
int N = int.Parse(Console.ReadLine());
int minPrimePalindrome = int.MaxValue;
for (int i = 2; i <= N; i++)
{
if (IsPrime(i) && IsPalindrome(i))
{
minPrimePalindrome = Math.Min(minPrimePalindrome, i);
}
}
Console.WriteLine(minPrimePalindrome == int.MaxValue ? -1 : minPrimePalindrome);
}
static bool IsPrime(int number)
{
if (number < 2) return false;
for (int i = 2; i <= Math.Sqrt(number); i++)
{
if (number % i == 0) return false;
}
return true;
}
static bool IsPalindrome(int number)
{
string str = number.ToString();
int len = str.Length;
for (int i = 0; i < len / 2; i++)
{
if (str[i] != str[len - 1 - i]) return false;
}
return true;
}
}
Code Explanation
1. Main Method: For the input integer N, it iterates through numbers from 2 to N.
It checks if each number is both prime and a palindrome, and finds the minimum value among them.
2. IsPrime Method: Determines whether the given number is prime.
If the number is less than 2, it returns false as it is not prime,
and it checks for divisibility from 2 to √number to determine its primality.
3. IsPalindrome Method: Converts the given number to a string and
checks if it is a palindrome by comparing characters from the front and back.
It returns true if all characters match.
Time Complexity
The time complexity of this algorithm is O(N√N).
This is because checking numbers up to N involves O(√N) time for primality testing for each number.
Therefore, as the input range increases, the computation time is affected, so it is important to consider this when writing the code.
Conclusion
Through the problems covered in this course, we have learned how to determine prime numbers and check for palindromes.
Understanding primes and palindromes is a common topic in coding tests,
so it is advisable to practice thoroughly.
Additionally, I recommend building your skills through a variety of practice problems.