7
\$\begingroup\$

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!

\$\endgroup\$

closed as off-topic by cat, Blue, a spaghetto, Alex A. Apr 18 '16 at 18:51

  • This question does not appear to be about programming puzzles or code golf within the scope defined in the help center.
If this question can be reworded to fit the rules in the help center, please edit the question.

  • \$\begingroup\$ @PeterTaylor whoops! Thought I had it "as less than or equal to." Edited that in. Thanks for the catch! \$\endgroup\$ – Hovercouch Jan 24 '14 at 6:06
  • 3
    \$\begingroup\$ I'm voting to close this question as off-topic because underhanded challenges are no longer on-topic on this site. meta.codegolf.stackexchange.com/a/8326/20469 \$\endgroup\$ – cat Apr 18 '16 at 15:23
9
\$\begingroup\$

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.
\$\endgroup\$
  • \$\begingroup\$ Did you arrive at that polynomial via Lagrange interpolation? (The upshot of which is: that polynomial is tailor-made for the eight numbers in the test cases, and you can tailor-make such a polynomial for any number of test pairs, though I'm not sure whether it always (mis)aligns properly with rounding issues.) \$\endgroup\$ – Jonas Kölker Jul 25 '14 at 17:21
  • \$\begingroup\$ Least-squares approximation, but the polynomial is still tailored. You would have to check on a case-by-case basis whether any false positives are generated. \$\endgroup\$ – user15259 Jul 25 '14 at 20:26
3
\$\begingroup\$

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
\$\endgroup\$
  • \$\begingroup\$ To achieve this in Matlab without the sneaky stuff, max(primes(input)) would suffice :) \$\endgroup\$ – mmumboss Jan 24 '14 at 13:59
2
\$\begingroup\$

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 ;)

\$\endgroup\$
2
\$\begingroup\$

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
\$\endgroup\$
1
\$\begingroup\$

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)

\$\endgroup\$
0
\$\begingroup\$

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.

\$\endgroup\$
0
\$\begingroup\$

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.

\$\endgroup\$

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