Miller-Rabin Primality Test and Caching V
Once concern about Miller-Rabin Primality Test is that it is a probability one. That's true. It can check for primality is O(Log(N)) which is the best that one can get, but probabilistically.
The probability of a false positive, however, is (1/4)^k, where k is the number of witnesses in your code. In my implementations I use k=100. Which makes the probability of a false positive equal to 1/(2^200). Now when I ask ChatGPT 5.1 for "what is like to have such a probability", one of its answers is:
A chance of 1/(2^200) is equivalent to picking one special atom in Earth at random and hitting the wrong atom by mistake, ten thousand times in a row.
Hence you're good. Example in this problem. Code is down below, cheers, ACC.
Largest Prime from Consecutive Prime Sum - LeetCode
ou are given an integer n.
Return the largest less than or equal to n that can be expressed as the sum of one or more consecutive prime numbers starting from 2. If no such number exists, return 0.
Example 1:
Input: n = 20
Output: 17
Explanation:
The prime numbers less than or equal to n = 20 which are consecutive prime sums are:
2 = 25 = 2 + 317 = 2 + 3 + 5 + 7
The largest is 17, so it is the answer.
Example 2:
Input: n = 2
Output: 2
Explanation:
The only consecutive prime sum less than or equal to 2 is 2 itself.
Constraints:
1 <= n <= 5 * 105
public class Solution {
static List listOfPrimes = null;
static PrimalityInt primesCache = null;
private void PopulateListOfPrimes(int n)
{
if (listOfPrimes == null)
{
listOfPrimes = new List();
primesCache = new PrimalityInt();
for (int i = 2; i <= n; i++)
{
if (primesCache.IsPrimeMillerRabin(i))
{
listOfPrimes.Add(i);
}
}
}
else
{
for (int i = listOfPrimes[listOfPrimes.Count - 1] + 2; i <= n; i+=2)
{
if (primesCache.IsPrimeMillerRabin(i))
{
listOfPrimes.Add(i);
}
}
}
}
public int LargestPrime(int n)
{
PopulateListOfPrimes(n);
int retVal = 0;
int currentSum = 0;
for (int i = 0; i < listOfPrimes.Count && currentSum + listOfPrimes[i] <= n; i++)
{
currentSum += listOfPrimes[i];
if(primesCache.IsPrimeMillerRabin(currentSum))
retVal = Math.Max(retVal, currentSum);
}
return retVal;
}
}
public class PrimalityInt
{
public static HashSet millerRabinCache = new HashSet();
public bool IsPrimeMillerRabin(int n)
{
if (millerRabinCache.Contains(n)) return true;
//It does not work well for smaller numbers, hence this check
int SMALL_NUMBER = 1000;
if (n <= SMALL_NUMBER)
{
bool val = IsPrime(n);
if (val) millerRabinCache.Add(n);
return val;
}
int MAX_WITNESS = 100;
for (int i = 2; i <= MAX_WITNESS; i++)
{
if (IsPrime(i) && Witness(i, n) == 1)
{
return false;
}
}
millerRabinCache.Add(n);
return true;
}
public int SqRtN(int N)
{
/*++
* Using Newton Raphson method we calculate the
* square root (N/g + g)/2
*/
int rootN = N;
int count = 0;
int bitLength = 1;
while (rootN / 2 != 0)
{
rootN /= 2;
bitLength++;
}
bitLength = (bitLength + 1) / 2;
rootN = N >> bitLength;
int lastRoot = 0;
do
{
if (lastRoot > rootN)
{
if (count++ > 1000) // Work around for the bug where it gets into an infinite loop
{
return rootN;
}
}
lastRoot = rootN;
rootN = (N / rootN + rootN) >> 1;
}
while (!((rootN ^ lastRoot) == 0));
return rootN;
}
public bool IsPrime(int n)
{
if (n <= 1)
{
return false;
}
if (n == 2)
{
return true;
}
if (n % 2 == 0)
{
return false;
}
for (int i = 3; i <= SqRtN(n) + 1; i += 2)
{
if (n % i == 0)
{
return false;
}
}
return true;
}
private int Witness(int a, int n)
{
long t, u;
long prev, curr = 0;
long i;
long lln = n;
u = n / 2;
t = 1;
while (u % 2 == 0)
{
u /= 2;
t++;
}
prev = ModPow(a, u, n);
for (i = 1; i <= t; i++)
{
curr = ModPow(prev, 2, lln);
if ((curr == 1) && (prev != 1) && (prev != lln - 1)) return 1;
prev = curr;
}
if (curr != 1) return 1;
return 0;
}
private long ModPow(long baseValue, long exponent, long modulus)
{
long result = 1;
baseValue %= modulus;
while (exponent > 0)
{
if ((exponent & 1) == 1)
{
result = (result * baseValue) % modulus;
}
baseValue = (baseValue * baseValue) % modulus;
exponent >>= 1;
}
return result;
}
} 
Comments
Post a Comment