Guest User

Untitled

a guest
Jan 20th, 2019
91
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 1.72 KB | None | 0 0
  1. boolean[]isPrime = new boolean [N/2+1];
  2.  
  3. boolean[]isPrime = new boolean [N+1];
  4.  
  5. for (int i = 3; i <= N; i=i+2) {
  6. isPrime[i] = true;
  7. }
  8.  
  9. for (int i = 3; i <= N; i=i+2) {
  10. if (isPrime[i]) primes++;
  11. ...
  12. }
  13.  
  14. Full code:
  15.  
  16. public class PrimeSieve {
  17. public static void main(String[] args) {
  18.  
  19. if (args.length < 1) {
  20. System.out.println("Usage: java PrimeSieve N [-s(ilent)]");
  21. System.exit(0);
  22. }
  23.  
  24. int N = Integer.parseInt(args[0]);
  25.  
  26. // initially assume all odd integers are prime
  27.  
  28. boolean[]isPrime = new boolean [N/2+1];
  29.  
  30. isPrime[2] = true;
  31.  
  32. for (int i = 3; i <= N; i=i+2) {
  33. isPrime[i] = true;
  34. }
  35.  
  36. int tripCount = 0;
  37.  
  38. // mark non-primes <= N using Sieve of Eratosthenes
  39. for (int i = 3; i * i <= N; i=i+2) {
  40.  
  41. // if i is prime, then mark multiples of i as nonprime
  42. if (isPrime[i]) {
  43. int j = i * i;
  44. while (j <= N){
  45. tripCount++;
  46. isPrime[j] = false;
  47. j = j + 2*i;
  48. }
  49. }
  50. }
  51.  
  52. System.out.println("Number of times in the inner loop: " + tripCount);
  53.  
  54. // count and display primes
  55. int primes = 0;
  56. if(N >= 2 ){
  57. primes = 1;
  58. }
  59. for (int i = 3; i <= N; i=i+2) {
  60. if (isPrime[i]) primes++;
  61. if (args.length == 2 && args[1].equals("-s"))
  62. ; // do nothing
  63. else
  64. System.out.print(i + " ");
  65. }
  66. System.out.println("The number of primes <= " + N + " is " + primes);
  67. }
  68. }
  69.  
  70. for (int i = 3; i <= N; i=i+2)
  71.  
  72. for (int i = 3; i <= N/2; i=i+2)
Add Comment
Please, Sign In to add comment