Posted in Code Competitions, General

Solved the TopCoder problem with least non-zero success rate

Background

Have anyone heard of PrePrime? Prime number is a number that is divisible by 1 and itself (it has 2 divisiors). PrePrime has 4 divisiors. For example, the 1st preprime is 6 (1, 2, 3 & 6). The numbers 6, 8, 11, 14 … are a sequence of PrePrimes.

The Problem

Find the nth preprime. Sounds simple, but there is a catch. The number n, can be upto 1 Million (1,000,000). So you are going to loop almost MaxInteger, then find if the number is pre prime. TopCoder wants code to respond back in 2 seconds. I broke 1 million into 100 parts. I pre-calculated every 10,000th PrePrime and struck the results in an array ino the code again. So if when i get a query to calculate 43,000th PrePrime. I first pick the 40,000th prime number and start working from there till i reach 43,000. Yeah, its precalculating 1/10,000th of the results. Unless we have a multi processor computer. I am not sure how to do it within 2 seconds. Anyway here is my code below…

using System;
using System.Text;
using System.Text.RegularExpressions;
using System.Collections;
using System.Collections.Generic;

public class PreprimeNumbers {
  //public List arr = new List();
/*{ 6, 
222599, 
460015, 
703553, 
951149 };*/
  public int[] arr = { 6, 41037, 85003, 130163, 175867, 222595, 269506, 316527, 364369, 411989, 460011, 508658, 557129, 606063, 654554, 703546, 752777, 802391, 851923, 901577, 951143, 1000543, 1050514, 1100566, 1150843, 1201429, 1251479, 1301977, 1352177, 1403067, 1453467, 1504507, 1554933, 1605621, 1656418, 1707686, 1758349, 1809493, 1860778, 1912201, 1963817, 2015207, 2066453, 2117989, 2169451, 2220565, 2272654, 2323769, 2374973, 2426881, 2478478, 2530498, 2582417, 2634307, 2686165, 2738161, 2790154, 2843041, 2894739, 2946639, 2998839, 3050557, 3102997, 3155605, 3208541, 3261109, 3313397, 3365095, 3418171, 3470639, 3522473, 3574502, 3627578, 3680114, 3733219, 3785423, 3838238, 3890966, 3944026, 3996329, 4049561, 4102397, 4154783, 4207979, 4260811, 4313255, 4365757, 4419037, 4472635, 4525643, 4578583, 4631906, 4685107, 4738661, 4791471, 4844693, 4898343, 4951795, 5005241, 5058386, 5111443 };
    public int nthNumber(int n) {
        int N=6;
    int i = 1;
    if (n > 10000)
    {
      i = n / 10000;
      N = arr[i];
      i = i * 10000;
    }

for (; i <= n; i++)
    {
      while(!IsPrePrime(N++));
      //if (i % 10000 == 0)
      //    Console.Write("{0}, ", N-1);
    }
        return N-1;
    }

private bool IsPrePrime(int n)
  {
    int l = (int)Math.Sqrt(n);
    int c = 0;
    for (int i = 2; i <= l; i++)
    {
      if (n % i == 0)
      {
        c++;
        if (c > 2)
          return false;
      }
    }
    c += c + 2;
    if (l * l == n)
      c--;
    return (c == 4);
  }
  //1 000 000
  //0 043 765
  //  500 000
} 
Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s