Your Ad Here

advanced code snippet search

Posted By

jaircazarin on 10/13/08


Tagged

math Algorithms Microsoft-Interview


Versions (?)

Who likes this?

4 people have marked this snippet as a favorite

jaircazarin
grassdog
sergeizen
skammer


Prime Numbers

 / Published in: C
 

Check whether a given numbers is a prime using different techniques.

Expand | Embed | Plain Text 
  1. #include<stdio.h>
  2. #include<math.h>
  3. #define MAX 1000
  4.  
  5.  
  6. int prime[MAX];
  7.  
  8. int isPrimeNaive(int n)
  9. {
  10. 	if(n <= 1)
  11. 		return 0;
  12. 	for(int i = 2; i < n; i++)
  13. 		if(n % i == 0)
  14. 			return 0;
  15. 	return 1;
  16. }
  17.  
  18. int isPrime(int n)
  19. {
  20. 	if(n<= 1)
  21. 		return 0;
  22. 	if(n == 2)
  23. 		return 1;
  24. 	if(n%2 == 0)
  25. 		return 0;
  26. 	int limit = (int)sqrt((double)n);
  27. 	for(int i = 3; i <= limit; i=i+2)
  28. 	{
  29. 		if(n % i == 0)
  30. 			return 0;
  31. 	}
  32. 	return 1;
  33. }
  34.  
  35. void sieve()
  36. {
  37. 	prime[0] = 0;
  38. 	prime[1] = 0;
  39. 	for(int i = 2; i < MAX; i++)
  40. 		prime[i] = 1;
  41. 	int limit = (int)sqrt((double)MAX);
  42. 	for(int i = 2; i <= limit; i++)
  43. 	{
  44. 		if(prime[i])
  45. 			for(int j = i*i; j <= MAX; j+=i)
  46. 				prime[j] = 0;
  47. 	}
  48. }
  49.  
  50. int isPrimeSieve(int n)
  51. {
  52. 	if(prime[n])
  53. 		return 1;
  54. 	else
  55. 		return 0;
  56. }
  57.  
  58. int main()
  59. {
  60. 	sieve();
  61. 	printf("N=%d %d\n", 1, isPrime(1));
  62. 	printf("N=%d %d\n", 2, isPrime(2));
  63. 	printf("N=%d %d\n", 3, isPrime(3));
  64. 	printf("N=%d %d\n", 4, isPrime(4));
  65. 	printf("N=%d %d\n", 7, isPrime(7));
  66. 	printf("N=%d %d\n", 9, isPrime(9));
  67. 	printf("N=%d %d\n", 13, isPrime(13));
  68. 	printf("N=%d %d\n", 17, isPrime(17));
  69. 	printf("N=%d %d\n", 100, isPrime(100));
  70. 	printf("N=%d %d\n", 23, isPrime(23));
  71. 	printf("N=%d %d\n", 1, isPrime(1));
  72. 	return 0;
  73. }

Report this snippet  

You need to login to post a comment.