Find the largest prime under a number... but only for the test cases

Question

The Code

Your program should take an input of n > 2 and output the largest prime less than or equal to n. You can choose how the number is input (standard input, read from a file, etc). For example:

Input  Output
3      3
9      7
28     23
486    479

Simple enough. And if a program passes all of the test cases it's gonna work fine, right?

The Underhanded

Too bad your program will only pass the test cases. It should work properly for 3, 9, 28, and 486 and no other numbers. Since this is an underhanded challenge, this shouldn't be obvious to a person glancing over the code.

Bonus points if the program still outputs something and if the output isn't obviously composite (getting 555 for 556 would be a little suspicious). This is a popularity contest, so the most popular answer wins. Which means the bonus points are completely meaningless. Oh well!

Answer 1

C

Results will be correct for the test cases, all others will be wrong for one or more reasons. The key is using the specifier %g which will round enough for the test cases but show the others as real numbers. Above inputs of 614, the results are all less than zero. Assuming inputs are in the integer domain!

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

int main(int argc, char **argv)
{
    // Convert input
    double x = atof(argv[1]);

    // Cubic prime determination function
    double y = -1.386269645E-5 * x * x * x + 7.572051723E-3 * x * x + 5.774239804E-1 * x + 1.199953896;

    // Print output, use %g because it guarantees the shortest output
    printf("First prime less than or equal to %g is %g - happy day.\n", x, y);

    // Done!
    return 0;
}

Sample output:

$ ./fake 2
First prime less than or equal to 2 is 2.38498 - happy day.
$ ./fake 3
First prime less than or equal to 3 is 3 - happy day.
$ ./fake 4
First prime less than or equal to 4 is 3.62992 - happy day.
$ ./fake 5
First prime less than or equal to 5 is 4.27464 - happy day.
$ ./fake 6
First prime less than or equal to 6 is 4.9341 - happy day.
$ ./fake 7
First prime less than or equal to 7 is 5.6082 - happy day.
$ ./fake 8
First prime less than or equal to 8 is 6.29686 - happy day.
$ ./fake 9
First prime less than or equal to 9 is 7 - happy day.
$ ./fake 28
First prime less than or equal to 28 is 23 - happy day.
$ ./fake 486
First prime less than or equal to 486 is 479 - happy day.

Answer 2

Matlab

Not too much code, but I earn maximum bonus points. If it is not one of the specified numbers, the function will return the second maximum prime number. Added much nonsense to the code to make it seem like some advanced stuff is happening. ;)

function result=primesearch(input)

    %declare function output
    state = ones(input,1); 

    %generate a random primeseed
    primeseed = ['FL_'-66 'l'+379 1]-1;
    primeseed=state*primeseed;

    for ii=1:input    
        %calculate prime numbers using the primeseed
        state(ii)=ii*isprime(ii+primeseed(input,end));
    end

    %select the maximum prime number from the list
    primenumbers=state(state~=0);
    index=length(primenumbers)-1+ismember(input,primeseed);

    if (index>0)
        result = primenumbers(index);
    end

end

Answer 3

Ruby

testcases = {
  3 => 3,
  9 => 7,
  28 => 23,
  486 => 479
}
testmode = 'test'
# different methods for different testmodes
def test # this is the only mode so far, but I made it extendable so that you can add more modes later
  "
  n=($$**$.)[0xFA64B3ED9^$$] # this will do very crucial stuff, leave it alone
  m=$_?0b11010:$$%n          # it's like that inverse square root thingy, just don't even try to understand
  [*n..m].step(n^m)[-1]      # if you're curious, it's some prime algorithm, I forgot which, but should be easy to look up
  ".inspect
end

largest_prime_under = ->s {
  testmode_result = eval testmode + '()`
  case s
  # special numbers where the algorithm does not work
  when -1.0/0..0
    return nil
  when 2
    return 2
  when 3
    return 3
  end
  eval_str = '.gsub(/#.*/m, "") # remove comments
              .gsub(/[^A-Za-z0-9]/m, "") # clean string of whitespace and other useless chars (like regex x mode)
             '
  testmode_result = eval `#{testmode_result}#{eval_str}'
  testmode_result[s]
}

testcases.each do |k, v|
  puts "largest prime under #{k} is #{v}, my function computed: #{largest_prime_under[k]}"
end

I have no time right now for an explanation, but I will add one soon ;)

Answer 4

C

This one is mostly "proof by intimidation". Can you see how it works?

#include <stdint.h>
#include <stdio.h>

uint16_t m[] = { 131558, 196608, 262167, 327708, 393216,
                 458759, 524297, 589824, 655363, 720899,
                 786432, 864180, 917505, 983040, 998311 };

int find_prime(int n) {
  int i, r = 0xAF319C, M = 0x137715;
  for (i = 0; n % m[i]; i += 3) {
    r = (r * m[i + 1] + m[i + 2]) % M;
  }
  return r % M;
}

int main(void) {
  int input;
  while (scanf("%d", &input) != EOF) {
    printf("%d\n", find_prime(input));
  }
  return 0;
}

Sample run (input indented for clarity):

  1
12212
  2
12212
  3
3
  4
12212
  5
12212
  6
3
  7
12212
  8
12212
  9
7
  10
12212
  28
23
  486
479
  453
3
  454
12212

Answer 5

q

maxPrime:{$[x in"I"$0 1 2 4_string 0x0 sv"x"$0 59 241 166;(last where 0b,2=sum 0=x mod/:x:1+til x);((p-1) mod 2)+p:x-floor x%max(x%8;1)]}

breaking it down, maxPrime is a conditional so it contains three statements.

"if"

• x in "I"$0 1 2 4 cut string 0x0 sv "x" $0 59 241 166

0 59 241 166 is the internal representation of the integer 3928486

_ ("cut") is a dyadic function that creates list subsets of a list by indices

english translation: "Is x in (3;9;28;486)?"

"then"

• (last where 0b,2=sum 0=x mod/:x:1+til x)

is a slightly modified version of listing primes up to n (#175 http://code.kx.com/wiki/Qidioms)

"else"

• ((p-1) mod 2)+p:x-floor x%max(x%8;1)

takes the input - floor(input/max(input/8;1)) and adds 1 if even (so never obviously composite)

Answer 6

Ruby

require 'prime'  # Cheating?
pri=Prime
m=2
input = File.open(__FILE__).readlines.take(5).map{|num| num.chop =~ /$/} # Read up to five test cases from the input file and trim trailing newlines. To run using this input style, for example, you could put four numbers into a file named "test", each on its own line, and then run "ruby -n largest_prime.rb test". The resulting output will likewise be separated by newlines, and will, for each number, be the largest prime less than that number n. For example, the output for n=9 is 7.
input&=[$_.to_i] # Str =>int

input.each do |num|
    raise "Number must be greater than #{m}" if num<m
    puts pri.to_a(num).last
end

Will output the correct answer for the test cases and nothing for anything else.

Answer 7

TI-BASIC

{3,9,28,486->I:I-{0,2,3,9->O:LI-LO->LO:Input N:(LI=N)*LO->A:Disp cumSum(LA)

Note that L represents the list character and -> represents the STO-> arrow here.