5 kyu

Master your primes: sieve with memoization

73 of 176GiacomoSorbi
Description
Loading description...
Memoization
Algorithms
Tutorials
View
AllIssues16Questions8Suggestions5Show Resolved
  • Please sign in or sign up to leave a comment.
  • tchaflich Avatar

    Is this meant to come with some code pre-written? Some languages have significant partial implementations, whereas other languages only have the bare-bones you usually see with kata.

    Languages with boilerplate only: Crystal, Python, Ruby

    Languages with solution partially implemented: C#, JavaScript

  • ahmet_popaj Avatar

    Great kata of the series on primes to learn more about dynamic programming and algorithms efficency.

  • SS-Stefanov1 Avatar

    Pretty sure that the JS random tests are not correct..

    In some cases it expects true for non-prime numbers (for example 992237) and the oposite as well (for example 373)

  • FelixRock Avatar

    what is kyu

  • goldenratio161 Avatar

    umm, what? (python)

    Testing for 653
It should work with random inputs too: True should equal False

    isn't 653 prime?

  • Quark Fox Avatar

    whats up with abs(len(primes)-9)<3 ? why at the same time kata is asking to update the primes array and not update??

  • foxy01 Avatar

    Wow I definitely can't get how you can check number 8855 with only first 22 prime numbers (the 22nd is number 79). Isn't the point of the kata to add the prime number only if it is not present in the list and it is not the divisor of the N?

    "Testing primes length after check for 8855 It should work with random inputs too: expected a result close to 22, instead got 525: False should equal True"

    The funny thing is that a lot of tests print the same error (doesn't matter if it's a large or small number):

    "Testing primes length after check for 119873 It should work with random inputs too: expected a result close to 22, instead got 525: False should equal True"

    "Testing primes length after check for 1025 It should work with random inputs too: expected a result close to 22, instead got 525: False should equal True"

  • user6720290 Avatar

    This is completely incoherent.

  • sj95126 Avatar

    I really don't understand what this wants me to do. I get the idea of not doing more work than you need to, but I'm apparently failing for not doing ENOUGH work, even though I'm doing exactly the right amount.

    Take this example; this test fails where the previous primes length test succeeded.

    Testing primes length after check for 74706941 It should work with random inputs too: expected a result close to 65, instead got 60: False should equal True

    The prime factor that establishes that 74706941 is not prime is 281. 281 is the 60th prime number, so I did exactly as much work as I needed to answer the question. Why should I have to have done more work than that?

  • Awesome A.D. Avatar

    Why is the preloaded code for C# riddled with errors?

    The base method the tests call is IsPrime but in the preloaded code it is called isPrime. The property Primes is a List<long> but the method body triese to access Primes.length (both a typo, it should be Length, but also incorrect because Lists don't have a Length property, they have Count). Finally it tries to call some mysterious ExpandPrimes method which is not defined anywhere. Why is that there? Is the purpose of this kata to implement this method? If so, the description doesn't mention that. In fact, the entire description is an oddly rambling mess, to be quite frank.

  • pa-m Avatar

    Go translation available.

  • B1ts Avatar

    Could someone please just explain what this kata really wants, regarding prime list length? I'm completely lost, reading description and discourse only adds more confusion...

    And you must write a function that checks if a given number n is a prime looping through it and, possibly, expanding the array/list of known primes only if/when necessary (ie: as soon as you check for a potential prime which is greater than a given threshold for each n, stop).

    Ok, so we're checking if n is prime.

    looping through it

    Looping through what? From a to b? primes?

    and, possibly, expanding the array/list of known primes only if/when necessary

    When is that? If we find that it's prime? Do we expand if we found it's not prime? How far should we expand - up to n? Just adding n?

    (ie: as soon as you check for a potential prime which is greater than a given threshold for each n, stop).

    threshold? What threshold?? I don't see it described anywhere.

    Are we checking for n's primality or are we checking for some potential primes? I don't get it.

    Test.assertEquals(Math.abs(primes.length-9)<3,true);

    If someone could explain exactly what primes should be present for this test, and why, it would be much appreciated.

  • FArekkusu Avatar

    Ruby 3.0 should be enabled.

  • akar-0 Avatar

    This comment has been hidden.

  • Munto Avatar

    Is it possible to have more infos when a test fail in Crystal for test_len()?
    It just says:

    Testing primes length after check for 6624671
Test Failed
Expected: true
     got: false

    It's a bit hard to guess what it expects

  • Wilmp Avatar

    I noticed a couple of errors. Using Python 3.6

    Testing for 72857 It should work with random inputs too: False should equal True This one is 41 x 1777 so not a prime

    Testing for 30053 It should work with random inputs too: False should equal True This one is 41 x 733 so not a prime

    Testing for 76938497 It should work with random inputs too: False should equal True This one is 31 x 2481887 so not a prime

  • mjsspencer Avatar

    This kata is poorly written, poorly described.

  • Nima155 Avatar

    Log 98033 It should work with random inputs too: False should equal True The tests expect this number to be a prime! but it is not a prime.Language is python.

  • Mercy Madmask Avatar

    Big problem in Python 2 and 3, the primality check is completely wrong. It even said 41 is not a prime number. I tried to submit for 5 min but coulnd't get below 2 wrong checks.

  • kubasulek2 Avatar

    In javaScript version given: var primes = [2, 3, 5, 7]; // length 4

    and: Test.describe("Basic tests",_=>{ Test.assertEquals(isPrime(1),false); Test.assertEquals(isPrime(2),true); Test.assertEquals(isPrime(5),true); Test.assertEquals(isPrime(143),false); Test.assertEquals(Math.abs(primes.length-5)<3,true); Test.assertEquals(isPrime(-1),false); Test.assertEquals(isPrime(29),true); //add here Test.assertEquals(isPrime(53),true); //add here Test.assertEquals(isPrime(529),false); Test.assertEquals(Math.abs(primes.length-9)<3,true); })

    primes.length === 6

    Last test cannot be passed: Math.abs(6-9) < 3;

    Also later i'm failing tests for primes.length;

  • dolamroth Avatar

    Python 2.7.6

    Testing for 76009410593 It should work with random inputs too: True should equal False

    https://www.wolframalpha.com/input/?i=76009410593+ 76009410593 is a prime number.

    Same for other 9 fails in my random tests.

  • Iron Fingers Avatar

    Testing for 683 It should work with random inputs too - Expected: false, instead got: true

    Not sure how it expects 683 not to be a prime while it is a prime. Many such failures.

  • anter69 Avatar

    You should probably disable require in ruby, otherwise it's (a bit) easier than expected. I think require = nil in the preloaded section is enough.

  • KataSideKick Avatar

    C# Translation added.Please review and approve~

    PS.fixed the markdown.

  • MDabrowski1990 Avatar

    This comment has been hidden.

  • cliffstamp Avatar

    Gia :

    This generator : 

    n = randint(1,10**randint(1,15))/6*6+(-1**randint(0,1))

    Produces wild swings in the test output so your own solution won't always pass and times out.

  • dev42 Avatar

    The primality check test passes but the length check test fails with below error. Is this a problem with the kata or should I continue to work on a more optimal solution which works with only 9 primes for checking primality of 15725?

    ERROR: Testing primes length after check for 15725 It should work with random inputs too: expected a result close to 9, instead got 30 - Expected: true, instead got: false

    Language is Ruby

  • docgunthrop Avatar

    The kata expects true for input 75647596379, but 75647596379 / 19 = 3981452441. Screenshot

  • cgte Avatar

    Hello, interestring kata for applying memoziation :) I have one question on the Python version : why testing with booleans ? Like : Test.assert_equals(abs(len(primes)-5)<3,True) Test.assert_equals(abs(len(primes)-9)<3, True)

    At first i used the global primes list that would fail on the first of the abose test, re declaring it in the function (so keeping the global one unchanged) made the fisrt of the above test succeed, but it's not a clean solution - and you loose previous computations. Such function may raise a TypeError for boolean inputs.

    Eventually printing n did not seem to work for boolean input, nothing to do with your kata but still annoying when debuging.

  • Blind4Basics Avatar

    Found those in the random tests:

    Testing primes length after check for 62478496948727
It should work with random inputs too: expected a result close to 1059, instead got 877: False should equal True

Testing primes length after check for 22375609223
It should work with random inputs too: expected a result close to 2188, instead got 1820: False should equal True

Testing primes length after check for 854393068157
It should work with random inputs too: expected a result close to 9384, instead got 7831: False should equal True

    Seems I find a "more efficient" (or at least, a "stop faster") version than yours, but that makes fail the tests. Not fair! But in addition, I get sometimes a time out anyway... (might be server issues...)

    To me, your kata still lacks some additionnal explainations about what we should do or not. Here, it seems more about guessing what you did exactly on your side.

  • MDabrowski1990 Avatar

    This comment has been hidden.

  • Voile Avatar

    This comment has been hidden.

  • imprezobus Avatar

    This comment has been hidden.

  • TinoC Avatar

    I'll be honest, the big challenge in solving this kata (Python version at least) was to figure out what the author intended to have for the length of primes[]. I happen to know a few things about primes, but this kata got me confused. I don't even know why I passed, and I won't try to figure it out.

  • anter69 Avatar

    OK, I'm afraid I don't understand what this kata wants, although I solved a few hundred here already... It seems to be clear, though:

    write a function that checks if a given number n is a prime...

    ...as soon as you find a prime which is greater than a given threshold for each n, stop).

    So, the initial list is [2, 3, 5, 7] and we start the tests:

    is_prime(1)    # False - not a prime
is_prime(2)    # True  - in the list
is_prime(5)    # True  - in the list
is_prime(143)  # not in the list, so let's start searching...
# after some calculations I find that it's not a prime
# and I stop at 149, which is the first prime > 143

# ...and here comes the twist:
abs(len(primes)-5)<3  # WTF?!
# 149 is the 35th prime, so how would be my list of primes shorter than 8???

    Please explain. I'm either stupid, or tired. Or the description is not clear.

  • anter69 Avatar

    Description is a bit broken:

    ...prime which is greater than a given threshold for each n, stop).

    Remove the backticks around 'n' or remove the bolding.

    Cheers

  • Voile Avatar

    Approved

  • Wittybit Avatar

    Oh, worst chicking ever. What i supposed to do with this error: It should work with random inputs too - Expected: true, instead got: false

    That is really anoying :~(

    P.S It passes 22 tests and fails 2 checks. Only 2(two), not more. Theay are in the middle when it trying to check value 715 for primness(if it is prime) P.P.S After submiting again(without any changes) getting next stats: 32 tests are passed and 14 checks are failed :C P.P.P.S Now constantly 50 passed / 40 failed :S P.P.P.P.S Lol, it passed after 100th click on submit :~) P.P.P.P.P.S But you should do something with it... please

    Anyway, nice optiomization problem =)

  • ecolban Avatar

    I think that this is related to the existing threads. I have tweaked my code so that I extend primes exactly as the tests expect it to be extended. Nevertheless, on input 4300816577, I get the error that my primes is only 6550 long, whereas 6551 is expected. The last prime in my primes is 65581, whose square is 4300867561, which is greater than 4300816577. Could you explain why you expect a longer sieve?

  • myjinxin2015 Avatar

    This comment has been hidden.

  • myjinxin2015 Avatar

    This comment has been hidden.