hacker.org

Code: Select all

import java.Math.BigInteger;

public class PrimalPi {
    private static final String sequence = "14159 [.................]"
    
    public static void main(String[] args)
    {
        for (int i=0; i<sequence.length(); i++) {
            System.out.println("Testing with startindex " + i);
            for (int j=sequence.length(); j>i; j--) {
                String totest_str = sequence.substring(i, j);
                char lastchar = totest_str.charAt(totest_str.length()-1);
                if (lastchar == '0' ||
                    lastchar == '2' ||
                    lastchar == '4' ||
                    lastchar == '5' ||
                    lastchar == '6' ||
                    lastchar == '8')
                    continue;

                BigInteger totest = new BigInteger(totest_str);
                if (totest.isProbablePrime(4)) {
                    System.out.println("Probable prime: " + totest_str);
                }
            }
        }
    }
}

Code: Select all

pow(2,n-1,n) == 1

Code: Select all

#include <stdio.h>
#include <gmp.h>

int main()
{

	mpz_t candidate;
	char pi[2049];
	
	mpz_init(candidate);
	scanf("%2048s",pi);
	
	int length=2049;
	int offset=0;
	char tempchar;
	
	while(--length)
		for(offset=0;offset<2049-length;offset++)
		{
			tempchar = pi[offset+length];
			pi[offset+length]=0;
			mpz_set_str(candidate,pi+offset,10);
			if(mpz_probab_prime_p(candidate,10)) return puts(pi+offset);
			pi[offset+length]=tempchar;
		}
	return 0;
}

Code: Select all

#This code is for the Primal Pi challenge on hacker(D0T)org.
#Written by stack.  (With a bit of leeched code)
#Runs in about 3-4 hours on my relatively fast computer.
#If you want to run this:
#Make a file with the first 2048 digits of pi and call it pi2048.txt in the same directory

import sys
import random

##### Start leeched Miller Rabin code:

def toBinary(n):
  r = []
  while (n > 0):
    r.append(n % 2)
    n = n / 2
  return r

def test(a, n):
  b = toBinary(n - 1)
  d = 1
  for i in xrange(len(b) - 1, -1, -1):
    x = d
    d = (d * d) % n
    if d == 1 and x != 1 and x != n - 1:
      return True # Complex
    if b[i] == 1:
      d = (d * a) % n
  if d != 1:
    return True # Complex
  return False # Prime

def MillerRabin(n, s = 50):
  for j in xrange(1, s + 1):
    a = random.randint(1, n - 1)
    if (test(a, n)):
      return False # n is complex
  return True # n is prime

##### The ABOVE modified Miller-Rabin code leeched from:
##### http://snippets.dzone.com/posts/show/4200
##### Why reinvent the wheel when you're too lazy to? ;)
##### I won't be commenting the Miller Rabin code for
##### you to understand.  That's what Wikipedia is for.

file = open("pi2048.txt")#Inside of pi2048.txt is the first 2048 digits of pi
pi=file.read()#Reads pi2048.txt into pi
file.close()#Frees up a bit of memory
pilen=len(pi)#Length of pi
glen=2 #Greatest length found (Changes while the code runs)

l=0
status=l-1
sys.stdout.write("Starting with ")
while l<pilen-200:
  m=glen
  while m<=2048:
    
    
#####Too lazy to make a longer sieve:
    if ((int(pi[l:m+l])%2!=0) and (int(pi[l:m+l])%3!=0) and (int(pi[l:m+l])%5!=0) and (int(pi[l:m+l])%7!=0) and (int(pi[l:m+l])%11!=0) and (int(pi[l:m+l])%13!=0) and (int(pi[l:m+l])%17!=0) and (int(pi[l:m+l])%19!=0) and (int(pi[l:m+l])%23!=0) and (int(pi[l:m+l])%29!=0) and (int(pi[l:m+l])%31!=0) and (int(pi[l:m+l])%37!=0) and (int(pi[l:m+l])%41!=0) and (int(pi[l:m+l])%43!=0) and (int(pi[l:m+l])%47!=0) and (int(pi[l:m+l])%53!=0) and (int(pi[l:m+l])%59!=0) and (int(pi[l:m+l])%61!=0) and (int(pi[l:m+l])%67!=0) and (int(pi[l:m+l])%71!=0) and (int(pi[l:m+l])%73!=0) and (int(pi[l:m+l])%79!=0) and (int(pi[l:m+l])%83!=0) and (int(pi[l:m+l])%89!=0) and (int(pi[l:m+l])%97!=0) and (int(pi[l:m+l])%101!=0)):
      if MillerRabin(int(pi[l:m+l]), 2):#First param is the number to test
                                         #Second param is the number of times
                                         #to run the test (the more times, the more accurate)
                                         #Because it only gives the probability of the number being a prime
                                         #Again, read more in Wikipedia
        print "-----"
        print "Loop: ", l
        print "Len: ", len(pi[l:m+l])
        print pi[l:m+l]
        glen=len(pi[l:m+l])-1
    if l>status:#Prints the status of the code
      print "Loop", l
      status+=100#Change this for the status to update more frequently
    m+=1
  l+=1

Code: Select all

	/**
	 * finds longest prime number in first 2048 decimal digits of pi
	 */
	public static void primes() {
		int bestlen=1977;int bestend=2003;
		for(int e=2050;e>bestlen+2;e--) {
			System.out.printf("\nending "+e+" on "+piDigits.substring(e-1,e));
			if ("024568".indexOf(piDigits.substring(e-1,e))<0) {
				for(int l=e-2;l>bestlen;l--) {
					BigInteger maybePrime = new BigInteger(piDigits.substring(e-l,e));  
					if (maybePrime.isProbablePrime(20)) {
						System.out.printf("match at "+e+" of length "+l);
						bestlen=l;bestend=e;
					} else {
						System.out.printf(".");
					}
				}
			}
		}
		System.out.printf("best match of length "+bestlen+" ending on "+bestend);
		writeToClipboard(piDigits.substring(bestend-bestlen,bestend));
	}

Code: Select all

{
	pidigits = 1415926535897932[...];
	found = 0;
	forstep(len = 2048,1,-1,
		for (start = 0,2048-len,
			part = (pidigits \ 10^start) % 10^len;
			if (ispseudoprime(part) && found == 0,print(part); found++);
		);
		if (found > 0, break);
	);
}