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.

  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.