ft_is_prime

소수(Prime Number) 구하기 효율적 알고리즘 :: 코드자몽

#include <unistd.h>

int	ft_is_prime(int nb)
{
	int	i;
	int	num;

	i = 2;
	num = 0;
	if (nb <= 1)
		return (0);
	if (nb == 2)
		return (1);
	else
	{
		while (i < nb)
		{
			if (nb % i != 0)
				num = 1;
			else
			{
				num = 0;
				break ;
			}
			i++;
		}
	}
	return (num);
}

이건 기계채점에서 OK가 떴지만, 타임 아웃이 발생할 가능성이 커서 다음과 같이 수정하였다.

#include <unistd.h>

int	ft_is_prime(int nb)
{
	long long	i;
	int			num;
	long long	nbb;

	i = 2;
	num = 0;
	nbb = nb;
	if (nbb <= 1)
		return (0);
	if (nbb == 2)
		return (1);
	while (i * i <= nbb)
	{
		if (nbb % i == 0)
		{
			num = 0;
			break ;
		}
		else
			num = 1;
		i++;
	}
	return (num);
}
/*
#include <stdio.h>
int	main(void)
{
	printf("%d",ft_is_prime(2147483647));
}
*/