Skip to content

Instantly share code, notes, and snippets.

@joriki
Created December 30, 2019 23:49
Show Gist options
  • Star 0 You must be signed in to star a gist
  • Fork 0 You must be signed in to fork a gist
  • Save joriki/0bf7b0349808003166f9161c657c5185 to your computer and use it in GitHub Desktop.
Save joriki/0bf7b0349808003166f9161c657c5185 to your computer and use it in GitHub Desktop.
Count the distinct prime factors and the divisors of even numbers between twin primes; see https://math.stackexchange.com/questions/3490592.
import java.util.Arrays;
public class Question3490592 {
final static int n = 0x40000000; // highest number to test
static boolean [] prime = new boolean [n / 2]; // prime [i] : is 2i + 1 prime?
public static void main (String [] args) {
Arrays.fill (prime,true);
// calculate the primes we need
int limit = (int) Math.sqrt (n); // highest factor to test
for (int p = 3;p <= limit;p += 2) // loop over odd integers
if (prime [p >> 1]) // only test primes p
for (int k = 3*p;k < n;k += 2*p) // loop over odd multiples of p
prime [k >> 1] = false; // sieve them out
double totalDivisors = 0;
long totalPrimeFactors = 0;
double pairDivisors = 0;
long pairPrimeFactors = 0;
long numberCount = 0;
long pairCount = 0;
for (int p = 3;p < 10000000;p += 2) {
int even = p + 1;
int sqrt = (int) Math.sqrt(even);
int divisorCount = 0;
int primeFactorCount = 0;
for (int d = 1;d <= sqrt;d++)
if (even % d == 0) {
divisorCount++;
if (d == 2 || ((d & 1) == 1 && prime [d >> 1]))
primeFactorCount++;
int s = even / d;
if (s == 2 || ((s & 1) == 1 && prime [s >> 1]))
primeFactorCount++;
}
divisorCount <<= 1;
if (sqrt * sqrt == n)
divisorCount--;
double divisorLog = Math.log(divisorCount);
totalPrimeFactors += primeFactorCount;
totalDivisors += divisorLog;
numberCount++;
if (prime [p >> 1] && prime [(p >> 1) + 1]) {
pairPrimeFactors += primeFactorCount;
pairDivisors += divisorLog;
pairCount++;
}
}
System.out.println("average prime factor count: " + totalPrimeFactors / (double) numberCount);
System.out.println("between prime factor count: " + pairPrimeFactors / (double) pairCount);
System.out.println("average disivor count logarithm: " + totalDivisors / (double) numberCount);
System.out.println("between disivor count logarithm: " + pairDivisors / (double) pairCount);
}
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment