14. 뒤집은 소수 (it 취업을 위한 알고리즘 문제풀이 입문 (with C/C++) : 코딩테스트 대비) ★★★☆☆

#include<stdio.h>

int reverse(int x){
	int r = 0; // ex> x = 123
	while(x != 0)
	{
		r *= 10; // 자리수 올림 r = 0; // r = 30 // r = 320;
		r += x % 10; // 1의 자리수 추출 후 더하기 r += 3; // r += 2; // r += 1;
		x /= 10; // 1의 자리수 빼고 자리수 내리기 x = 12; // x = 1 // x = 0;
	}
	return r; // r = 321
}

bool isPrime(int x){
	bool _isPrime = true;
	if(x == 1) return false;
	for(int i = 2; i < x; i++)
	{
		if(x % i == 0)
		{
			_isPrime = false;
			break;
		}
	}
	return _isPrime;
}

int main(){
	int a, num, r = 0;
	scanf("%d", &a); // 숫자 개수 입력
	for(int i = 0; i < a; i++)
	{
		scanf("%d", &num); // 숫자 입력
		r = reverse(num);
		if(isPrime(r))
			printf("%d ", r); 
	}
}

1. 정수 숫자 뒤집는 방법

 

int r = 0;

int x = 123
while(x != 0)
{
    r *= 10; // 자리수 올림 r = 0; // r = 30 // r = 320;
    r += x % 10; // 1의 자리수 추출 후 더하기 r += 3; // r += 2; // r += 1;
    x /= 10; // 1의 자리수 빼고 자리수 내리기 x = 12; // x = 1 // x = 0;
}

--> r = 321

 

2. n이 소수 확인하는 방법(시간복잡도 O(N))

소수는 1과 자기 자신을 제외한 약수가 없는 수를 말한다. 즉 0과 1은 소수가 아니므로 n을 2부터 나누어가면서

n-1까지 확인한다.