7
\$\begingroup\$

You are given n (200 ≤ n < 250) as a command line argument. Print 10 prime numbers with n digits. Your program should run under 1s and must be shorter than 5000 bytes (excluding).

Sum the digits of all your 500 primes. Program with the largest sum wins.

An example (more here):

$ ./find_large_primes 200
58021664585639791181184025950440248398226136069516938232493687505822471836536824298822733710342250697739996825938232641940670857624514103125986134050997697160127301547995788468137887651823707102007839
29072553456409183479268752003825253455672839222789445223234915115682921921621182714164684048719891059149763352939888629001652768286998932224000980861127751097886364432307005283784155195197202827350411
41184172451867371867686906412307989908388177848827102865167949679167771021417488428983978626721272105583120243720400358313998904049755363682307706550788498535402989510396285940007396534556364659633739
54661163828798316406139641599131347203445399912295442826728168170210404446004717881354193865401223990331513412680314853190460368937597393179445867548835085746203514200061810259071519181681661892618329
71611195866368241734230315014260885890178941731009368469658803702463720956633120935294831101757574996161931982864195542669330457046568876289241536680683601749507786059442920003278263334056542642264651
28591045597720075832628274729885724490653298360003309382769144463123258670807750560985604954275365591715208615509779345682419533206637382048824349415329839450792353652240682445321955199147316594996133
49790921912819110019003521637763748399072771256062128988437189616228355821145834783451215869998723492323628198577054239101181556609916127864608488018093426129641387774385490891035446702272744866010729
15474811206486587193258690501682404626361341756658894201908294153626080782693777003022566996735796983239343580281979005677758015801189957392350213806122307985157041153484138150252828152419133170303749
12654646219963267405298825104551142450213038420566798208417393291567314379831789259173233506811083774527183953999862675239292185131178671317061020444490733287588383918793095608410078925861028249824377
40992408416096028179761232532587525402909285099086220133403920525409552083528606215439915948260875718893797824735118621138192569490840098061133066650255608065609253901288801302035441884878187944219033

You can use this program to test for primality.

EDIT:

Use the following program to compute your score:

#!/usr/bin/python
# Usage: ./v.py ./find_large_primes

import subprocess
import sys

sum_ = 0
for n in xrange(200, 250):
  p = subprocess.Popen(
                   args=[sys.argv[1], str(n)],
                   stdout=subprocess.PIPE)
  p.wait()

  sum_ += sum(int(e) for e in p.stdout.read() if e.isdigit())
  p.stdout.close()

print sum_
\$\endgroup\$
  • 1
    \$\begingroup\$ Which 500 primes do we sum? Run the program 50 times? \$\endgroup\$ – Keith Randall Jun 23 '11 at 16:14
  • 1
    \$\begingroup\$ You should be able to print 500 different integers, 10 for each value of n = 200..249. So yes, run the program 50 times. \$\endgroup\$ – Alexandru Jun 23 '11 at 16:23
  • 1
    \$\begingroup\$ Do I get to use a quantum computer to solve it? \$\endgroup\$ – Neil Jun 30 '11 at 16:32
3
\$\begingroup\$

C++ with GMP

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

int main(int argc, char *argv[]) {
  int d = atoi(argv[1]);
  int i = 0;
  mpz_t n;
  mpz_init(n);
  mpz_ui_pow_ui(n, 10, d);
  mpz_sub_ui(n, n, 1);
  while (i < 10) {
    if (mpz_probab_prime_p(n, 100)) {
      printf("%s\n", mpz_get_str(NULL, 10, n));
      i += 1;
    }
    mpz_sub_ui(n, n, 2);
  }
}

It runs in just under a second on my machine. I'm too lazy to run it 50 times and sum up the digits, but it should be pretty good, as most of the digits (all but the last 4 of each number) are 9s.

> ./a.out 250
9999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999967
9999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999323
9999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999017
9999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999998731
9999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999997471
9999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999996959
9999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999995077
9999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999993529
9999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999993511
9999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999992459
\$\endgroup\$
  • \$\begingroup\$ Your score is: 1002616. GMP makes it so easy. \$\endgroup\$ – Alexandru Jun 23 '11 at 17:02
  • \$\begingroup\$ You might be able to improve it slightly if you can find numbers where only one or two digits are not 9, but they don't necessarily have to be at the end of the number... \$\endgroup\$ – mellamokb Jun 23 '11 at 17:03
  • 4
    \$\begingroup\$ @mellamokb: True. I'll let someone else try that... \$\endgroup\$ – Keith Randall Jun 23 '11 at 17:18
  • \$\begingroup\$ That is C, not c++ \$\endgroup\$ – kyle k Jan 10 '14 at 2:34
  • 1
    \$\begingroup\$ @kylek: It's both. \$\endgroup\$ – Keith Randall Jan 10 '14 at 7:25
1
\$\begingroup\$

Perl

use Math::Prime::Util ":all";
my $n = "1"."0"x shift;
print $n=prev_prime($n),"\n" for 1..10;

score 1002616, On 4770K, takes about 0.1s for an argument between 200 and 250; under 4 seconds for the score program. Time for a given run stays under 1s until 455 digits. Note that the Math::Prime::Util and Math::Prime::Util::GMP modules should be installed.

prev_prime uses ES BPSW as the primality test, so a little more stringent than Pari's precprime.

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.