Question

How do I Write a program called primecount that generates primes up to 1000000000 using the sieve of Erastosthenes and then counts the number of primes less than or equal to each of the numbers 10, 100, 1000, 10000, 100000, 1000000, 10000000, 100000000, and1000000000. The prime number theorem says that for large values of n, the number of primes less than or equal to n (π(n)) is approximately n / ln n. Print 4 columns, each in a field of with 10 separated by single spaces. The first is n, the second is π(n), the third is n / ln n, and the fourth is &pi(n) / (n / ln n). Your output should look like this.

---------- ---------- ---------- ----------
         n      pi(n)   n / ln n      ratio
---------- ---------- ---------- ----------
        10          4          4      0.921
       100         25         22      1.151
      1000        168        145      1.161
     10000       1229       1086      1.132
    100000       9592       8686      1.104
   1000000      78498      72382      1.084
  10000000     664579     620421      1.071
 100000000    5761455    5428681      1.061
1000000000   50847534   48254942      1.054
---------- ---------- ---------- ---------

Answer 1

Java Program:

---------------------------

import java.math.BigDecimal;
import java.math.RoundingMode;
import java.text.DecimalFormat;
import java.util.Arrays;

public class PrimeCount {
  
   private static final long N = 1000000000l;
  

   public static void main(String[] args) {
       PrimeCount pc = new PrimeCount();
       System.out.println("-------------------------------------------------");
       System.out.println(String.format("%s%10s%10s%10s", new Object[] { "n ", "pi(n) ", "n/ln n ", "ratio "}));
       System.out.println("-------------------------------------------------");
       for(int i = 10 ; i <= N ; i = i * 10) {
           long a = pc.piN(i);
           long b = pc.nBylnN(i);
           System.out.print(i);
           System.out.print(String.format("%10s", a));
           System.out.print(String.format("%10s", b));
           System.out.print(String.format("%10s", pc.ratio(a, b)));
           System.out.println();
       }
   }
  
   private long piN(int n) {
       // Create a boolean array "prime[0..n]" and initialize
// all entries it as true. A value in prime[j] will
// finally be false if j is Not a prime, else true.
boolean prime[] = new boolean[n + 1];
Arrays.fill(prime, true);
for(int j = 2 ; j * j <= n ; j++) {
// If prime[j] is not changed, then it is a prime
if(prime[j]) {
// Update all multiples of j
for(int k = j * j ; k <= n ; k += j) {
   prime[k] = false;
}
}
}
long c = 0l;
// Count all prime numbers
for(int j = 2 ; j <= n; j++) {
if(prime[j]) {
   c++;
}
}
       return c;
   }
  
   private long nBylnN(int n) {
       BigDecimal result = new BigDecimal(n / Math.log(n));
       long whole = result.longValue();
       double fraction = result.doubleValue() - whole;
       return fraction < 0.5d ? whole : ++whole;
   }
  
   private double ratio(double n, double d) {
       double r = (n / d);
       BigDecimal result = new BigDecimal(r);
       long whole = result.longValue();
       double fraction = result.doubleValue() - whole;
       DecimalFormat df = new DecimalFormat("#.###");
       df.setRoundingMode(fraction < 0.5d ? RoundingMode.FLOOR : RoundingMode.CEILING);
       String str = df.format(result.doubleValue());
       return Double.parseDouble(str);
   }

}
Output:

---------------------------

-------------------------------------------------
n pi(n) n/ln n ratio
-------------------------------------------------
10 4 4 1.0
100 25 22 1.136
1000 168 145 1.158
10000 1229 1086 1.131
100000 9592 8686 1.104
1000000 78498 72382 1.084
10000000 664579 620421 1.071
100000000 5761455 5428681 1.061
1000000000 50847534 48254942 1.053
-------------------------------------------------