Carmichael Numbers

Question

EDIT: I am changing the challenge.

Write a program to print Carmichael numbers. The challenge is to print the maximum number of them in less than 5 secs. The numbers should be in increasing order. Please do not use built in functions. Also please don't store the carmichael numbers in any form. To keep a common time measurement use Ideone. The program to print the maximum number of Carmichael number wins.

Sample Output
561
1105
1729
2465
2821
6601
8911
.
.
.

OEIS A002997

Answer 1

Python

This generates 1332 Carmichael numbers in under 5 seconds. Remove the print to actually get ideone to run to completion.

N=180000

maxprime = 18*N+1
prime = [1]*maxprime
prime[0] = prime[1] = 0
for i in xrange(maxprime):
  if prime[i]:
    for j in xrange(2*i,maxprime,i):prime[j]=0

for i in xrange(N):
  a=6*i+1
  b=12*i+1
  c=18*i+1
  if prime[a] and prime[b] and prime[c]:print a*b*c

Note that you could make this a whole lot faster in C.

Answer 2

unGolf3D dear Java :) maxCount=1193221 (at my local) and 552721 (at ideone) in 4.8s

    public class Main{
    public static void main(String[] args){
          long start=System.currentTimeMillis();
          int N=1200000;
          int list[]=new int[N];
            for (int i=0;i<N;i++) {
                list[i]=(i+1);
            }
            for (int i=1;i<N;i++) {
                if (Math.sqrt(list[i])-Math.floor(Math.sqrt(list[i]))==0) {
                    for (int j=i;j<N;j+=(i+1)){
                        list[j]=-1;
                    }
                }
            }
        boolean Carmichael=false;
        int chemCount=0;
        int product=1;
          for(int i=561  ;(System.currentTimeMillis()-start)/1000.0<=5;i++){
              if(!isPrime(i)&&list[i-1]==i){
                  for(int div=2;div<Math.sqrt(i);div++){
                      if(i%div==0 && isPrime(div)){
                          if((i-1)%(div-1)==0){
                              Carmichael= true;
                              product*=div;
                              chemCount++;
                              if (product==i) break;
                              }
                          else{
                              Carmichael=false;
                              break;
                              }
                      }
                  }
                  if (Carmichael && chemCount>=3 && product==i)
                      System.out.println(i);
                  Carmichael=false;
                   chemCount=0;
                   product=1;
              }
          }
  }

        static boolean isPrime(long number){
            if (number==2)
                return true;
            if (number==1)
                return false;
            for (long i=2;i<=Math.sqrt(number);i++) {
                if (number%i==0)
                    return false;
            }
            return true;
        }
    }

My JVM gets this to 1193221 number in 5 sec... I am sure this is slower than any other scripting languages and algo!! :( ... OTOH, http://www.ideone.com/clone/oNJin fails to create this big process.. calculates upto 552721 in 4.8 sec and breaks after that throwing http://en.wikipedia.org/wiki/SIGXCPU :)

Answer 3

C++

Machine i5-760 @ 2.8Ghz, only one core used

Numbers found in 5 seconds: 129

#define WIN32_MEAN_AND_LEAN
#include <windows.h>
#include <iostream>
using namespace std;

bool IsPrime (int v)
{
  bool
    is_prime = true;

  for (int i = 3, i2 = 9 ; i2 < v ; ++i, i2 += i + i + 1)
  {
    if (v % i == 0)
    {
      is_prime = false;
      break;
    }
  }

  return is_prime;
}

int Prime (int i, int &i2)
{
  static int
    primes [10000] = {2, 3, 5},
    primes2 [10000] = {4, 9, 25},
    num_primes = 3;

  while (i >= num_primes)
  {
    int 
      v = primes [num_primes - 1];

    do
    {
      v += 2;
    } while (!IsPrime (v));

    primes [num_primes] = v;
    primes2 [num_primes] = v * v;
    ++num_primes;
  }

  i2 = primes2 [i];
  return primes [i];
}

bool IsCarmichael (int n) 
{
   if (n < 2) 
   {
      return false;
   }

   int
     k = n--,
     i2 = 4;

   for (int i = 1, p = 2 ; i2 <= k ; p = Prime (i++, i2))
   {
      if (k % p == 0) 
      {
         k /= p;

         if (k % p == 0 || n % (p - 1) != 0)
         {
            return false;
         }

         i = 0;
      }
   }

   return --k != n && n % k == 0;
}

int main ()
{
  DWORD
    end = GetTickCount () + 5000;

  int
    count = 0,
    n = 561;

  while (GetTickCount () < end)
  {
    for (int i = 0 ; i < 1000 ; ++i)
    {
      if (IsCarmichael (n))
      {
        ++count;
        cout << n << endl;
      }
      ++n;
    }
  }

  cout << count << " Carmichael numbers found out of " << (n - 561) << " values tested." << endl;
}