fork download
copy 
  1. #include<stdio.h>
  2. #include<stdlib.h>
  3. typedef long long ll;
  4. ll expo(ll a,ll b,ll mod)
  5. {
  6. 	ll result=1;
  7. 	while(b)
  8. 	{
  9. 		if(b&1)
  10. 			result=(result*a)%mod;
  11. 		a=(a*a)%mod;
  12. 		b/=2;
  13. 	}
  14. 	return result;
  15. }
  16. int isprime(ll n)
  17. {
  18. 	if(n<2)			//special numbers
  19. 		return 0;
  20. 	if(n==2)		//prime number
  21. 		return 1;
  22. 	if(n%2==0)		//composite numbers
  23. 		return 0;
  24. 	ll d=n-1;
  25. 	ll count=0;
  26. 	while(d%2==0)
  27. 	{
  28. 		d/=2;
  29. 		count++;
  30. 	}
  31. 	//printf("count = %lld   for n = %lld\n",count,n);
  32. 	ll a;
  33. 	for(long long iter=0;iter<2;iter++)
  34. 	{
  35.  
  36. 		a=2+(rand()%(n-2));
  37. 		ll temp=expo(a,d,n);
  38. 		if(temp==1 || temp==n-1)
  39. 			continue;
  40. 		long long flag=0;
  41. 		for(long long i=0;i<count-1;i++)
  42. 		{
  43. 			temp=(temp*temp)%n;
  44. 			if(temp==1)
  45. 				return 0;
  46. 			if(temp==n-1)
  47. 			{
  48. 				flag=1;
  49. 				break;
  50. 			}
  51. 		}
  52. 		if(flag==1)
  53. 			continue;
  54. 		else
  55. 			return 0;
  56. 	}
  57. 	return 1;
  58. }
  59. int main()
  60. {
  61. 	long long test;
  62. 	ll input;
  63. 	scanf("%lld",&test);
  64. 	while(test--)
  65. 	{
  66. 		scanf("%lld",&input);
  67. 		for(long long i=input-1;i>0;i--)
  68. 			if(isprime(i))
  69. 			{
  70. 				printf("%lld\n",i);
  71. 				break;
  72. 			}
  73. 	}
  74. 	return 0;
  75. }
Success #stdin #stdout 0s 2116KB
comments (?)
stdin
copy 
3
5 
10
17
stdout
copy 
3
7
13
https://ideone.com/Zs26PV
language:
C99 (gcc 8.3)
created:
8 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!