Phantom's Python Challenge

View as PDF
Submit solution
Points: 40 (partial)
Time limit: 1.8s
Memory limit: 768M
Author:
quantum
Problem type
Allowed languages
Python

After all the ordeal, Christine decided to save your lives by kissing the Phantom. That was very nice of her. However, the Phantom considers letting Christine leave with Raoul, if and only if you can convince him that your party is worthy. He challenges you to write a program that shows all the primes under a specific number, while marking the twin primes. Easy as it may sound, the Phantom is also an expert programmer: you have to prove yourself to be at least as good as him. In Python, he expects you to write it in one statement. This means, no newlines or semicolons are allowed. To prevent the cheap way of achieving this, you are also not allowed to use eval or exec. To make sure he did not save that scarf for nothing, Raoul bribes you with 40 staggering points.

Input Specification

The input will be one line, containing the number N, such that N \in \{50, 100, 1\,000, 1\,000\,000, 10\,000\,000\}.

Output Specification

All the primes smaller than N, separated by whitespace, with a * after every number forming a twin prime with another. A twin prime is defined as a prime number n such that n-2 or n+2 are prime.

Scoring

If your solution is correct and contains only one statement without eval or exec, you get 10 points. For full points, your solution must be at most 114 characters long.

More accurately, let L be the length of your solution. If your solution is wrong, you receive 0. If L \ge 160, you get \left(\dfrac{160}{L}\right)^2 \times 20 + 10 points. If L < 160, your score is \min\left(40, 40 - 10 \times \dfrac{L-114}{46}\right).

Sample Input

50

Sample Output

2
3*
5*
7*
11*
13*
17*
19*
23
29*
31*
37
41*
43*
47

Comments


  • 5
    Sucram314  commented on Jan. 28, 2023, 10:50 p.m. ← edit 2

    BRO WHY DO I HAVE 100/100 BUT NO FULL AC

    Edit: HALP ME I HAVE ONE CHAR TOO MANY AAAAAAAAAAAA

    Edit 2: I DID IT LESGOOOOOOOOOOOOOOOOOOOOOOOOOOOO


  • 4
    prophet  commented on April 11, 2020, 8:41 p.m.

    Is the full solution possible in python 3? All of the best submissions are in python 2.


    • 3
      Dingledooper  commented on Jan. 22, 2022, 9:50 p.m.

      PyPy3 has apparently upgraded to 3.8, allowing for solutions that abuse the walrus operator. Consequently, 108 bytes seems to be the new record (beating the best Python 2 solutions by over 4 bytes).


    • 3
      Dingledooper  commented on Dec. 18, 2020, 2:49 a.m. ← edited

      Due to my discovery of a 114-byte solution in Python 2, it now appears possible in Python 3.


      • -19
        c  commented on Dec. 18, 2020, 8:05 p.m.

        This comment is hidden due to too much negative feedback. Show it anyway.


    • 4
      AussieSeaweed  commented on Dec. 9, 2020, 4:19 a.m. ← edited

      There is a 116 character solution in Python 3 with the correct time complexity, but it TLEs.

      Edit: There is a 106-byte solution that passes in PyPy 3


    • 4
      institutionalisation  commented on Sept. 5, 2020, 8:37 p.m. ← edited

      No it's not possible in python 3, sorry. Python 2 has a lot of quirks in its syntax that make it easier to golf.

      2022 Edit: Dingledooper's right, it is now possible in Python 3


  • 3
    prophet  commented on April 10, 2020, 12:58 a.m.

    Note: As an extension of eval/exec cheating, compile is also not allowed.


  • 6
    Zeyu  commented on Jan. 23, 2019, 4:41 p.m. ← edit 2

    Looking from the sample input, are we assuming that 1 is a prime as well since 3 is considered a twin prime?

    EDIT: Misread the "or", my bad


  • 0
    institutionalisation  commented on Nov. 27, 2017, 11:54 p.m.

    Help please. What's causing my code to MLE? sys.getsizeof(set([*range(int(1e7))])), the maximum size of my sieve, returns 134217844 \simeq 130MB on my computer. Why is my code using so much more than that?


    • 4
      kipply  commented on Nov. 28, 2017, 12:06 a.m.

      Pypy, despite fast is not very efficient with memory.


      • 0
        institutionalisation  commented on Nov. 28, 2017, 12:19 a.m.

        My code TLEs on PY3 but would otherwise still MLE.


  • 2
    echofox  commented on Sept. 25, 2017, 5:49 p.m. ← edited

    e: help


    • 12
      Xyene  commented on Sept. 25, 2017, 6:39 p.m.

      Work on it for more than 2 hours 😃


      • 3
        echofox  commented on Sept. 25, 2017, 11:00 p.m.

        blasphemy :o


  • 10
    GaryZ  commented on April 8, 2015, 3:44 a.m.

    Thanks for the fun problem, guys!


    • 18
      FatalEagle  commented on April 8, 2015, 3:52 a.m.

      Never did I think I would see the day someone actually solves this problem.


    • 6
      quantum  commented on April 8, 2015, 3:47 a.m.

      Good job. Now try to make it even shorter!


      • 21
        GaryZ  commented on April 8, 2015, 3:51 a.m.

        Too late, I peeked at your code.