3 kyu
Prime counting
Loading description...
Mathematics
Recursion
Algorithms
Memoization
Performance
Number Theory
View
This comment has been reported as {{ abuseKindText }}.
Show
This comment has been hidden. You can view it now .
This comment can not be viewed.
- |
- Reply
- Edit
- View Solution
- Expand 1 Reply Expand {{ comments?.length }} replies
- Collapse
- Spoiler
- Remove
- Remove comment & replies
- Report
{{ fetchSolutionsError }}
-
-
Your rendered github-flavored markdown will appear here.
-
Label this discussion...
-
No Label
Keep the comment unlabeled if none of the below applies.
-
Issue
Use the issue label when reporting problems with the kata.
Be sure to explain the problem clearly and include the steps to reproduce. -
Suggestion
Use the suggestion label if you have feedback on how this kata can be improved.
-
Question
Use the question label if you have questions and/or need help solving the kata.
Don't forget to mention the language you're using, and mark as having spoiler if you include your solution.
-
No Label
- Cancel
Commenting is not allowed on this discussion
You cannot view this solution
There is no solution to show
Please sign in or sign up to leave a comment.
This comment has been hidden.
No, you are miles away from an efficient approach. You need to figure out another way to count primes.
Are the test cases always going to be primes, or do I have to check for that too?
although unfortunately my solution also time out, and i couldn't optimize my code to not time out.....so i decided to look at the solutions and run them...to my surprise i found that when i ran any of the solutions they all time out!!! how is this possible?are there any solutions that could accept time out?if so, why in my case couldn't i accept time out?
This happened in what language? Its possible that tests used to be weak, accepted slow solutions, and later got hardened, but the old, slow solutions didnt get marked as invalid.
Or maybe the language version was updated, and is, for some reason, slower than the older one.
Did you check the newest, recently published solutions, or the top voted, possibly old ones?
as shown in my solution I have coded my code in Python
user monadius' solution appeared first and I ran it with the following result: "Timed OutPassed: 275Failed: ?Exit Code: 1 Test Results: Basic tests (4 of 4 Assertions) 100 random tests for n <= 10^6 (100 of 100 Assertions) 100 random tests for n <= 2*10^7 (100 of 100 Assertions) 50 random tests for n <= 10^9 (50 of 50 Assertions) 20 random tests for n <= 10^10 (20 of 20 Assertions) [Code length requirement] Solution should be 3000 characters or less STDERR Execution Timed Out (12000 ms)"
it is acceptable to me if I can run a Python code here on the Codewars UI that does not time out when run....so can someone show me a code that does NOT time out?
bad exercise,
help...what should I use? I take 207 tests, but no more. or does 254+, but everything is wrong
This comment has been hidden.
This comment has been hidden.
Remember, this kata wants you to count primes, not to know them.
Tried several ways to do this but keep timing out at the higher levels. Anyone who completed willing to give a hint?
Is the correct solution to use a sieve to generate the primes or to use a formula to determine the number? When I try the former it keeps timing out, when I try the latter none of the libraries that have the needed functionality seem to be available.
This seems impossible i used 6n+1, 6n-1 theorem which means that i'm reducing the loops by 66.67%.In my IDE it runs in 7.11 secs for 10000000.However here, it shows tle.
I guess you are supposed to implement a quick algorithm to count primes. You have
numpy
andgmpy2
to help you dealing with a fast implementation.those libraries are not required, you need to
come up withresearch a specific "prime counting" algorithmAs I understand it, "come up with" means research. Unless you are a mathematician by trade :P
that's what I said o_O
The kata doesn't even specify which libraries are blocked. All the formula-based ones I can find require scipy which appears to be blocked. Am I to understand that the only way to solve this is to construct the prime counting theorem from scratch? That's not really a coding exercise to to speak.
The kata does not block Scipy, it's simply not installed on Codewars.
@abrunk read which libraries you can use here: https://docs.codewars.com/languages/python
SciPY is on the list of available libraries in the above link, but I cannot access it for the purposes of this kata.
That's weird, in some other kata seems to work. At least, it doesn't throw an error when importing it. Maybe it's related to the characters limit?
Right? That's why I said i thought it was blocked by this kata without that rule being specified in the instructions.
no libraries are blocked in this kata, there is only the code character count limit
bad exercise.
Hi I've tried everything that I could but still I have problem with execution time. my program manage to solve maximum 114 problems. What can I do with it??
Hello, I've been looking for a solution for two days now. 202 tests is my maximum. I give up.
this is a very specific problem, and has a very specific solution
This comment has been hidden.
i tried that approach and found that it's not possible to generate 10^10 primes in the time given. you should use a wikipedia page that discusses what the kata is about.
Something weird is going on here.
I wrote up a simple Sieve for this, but I can't seem to get it to fail in consistent ways. The main issue that I'm experiencing is that I'm timing out, and I accept that, but I'm also failing test cases in off-by-one ways, and that's something I can't stand. As an example, for one attempt, I'll get a test error that says:
and that will be the only test error that isn't the timeout, and for the next test, where I only change the whitespace, I'll get two errors:
It would be good to know what test
n
I actually fail wheren
is passed into the function. It would be more helpful to change the text that reports an error to be something like "There are {correct_count} of primes below {passed_in_n}, code returned {n}."This comment has been hidden.
You should count primes "less than or equal to some natural
n
". But you do not includen
whenn
is prime.great, I had the same problem.
@monadius - your "resolution" to the raised issue... isn't isn't a resolution. The issue that I'm raising here is that the error output messages of failed tests are insufficient to diagnose the errors. If I don't have the
n
that is being passed in to my function, I can't figure out why my function is incorrect. Alongside this, the provided tests don't have any prime numbers - for example, it would be helpful to have something like7
as a simple test to validate that my code works when provided with a prime number. There's probably something like amessage
field in theassert_equals
function call that your unit test provides - it should be as simple as changing the unit test to be something like this:Please review: C++ Translation
I'd be very grateful @monadius
It seems, most solutions got invalidated due to buffer overload. And it's partially due to reference solution, which also takes a lot of memory.
I'm sorry, I didn't quite understand the problem
Reference solution and people's solutions compute something, that takes a lot of memory (more than maximum buffer size 1.5 MB allowed)
What exactly do you call a "Reference solution"?
This comment has been hidden.
If I understood you correctly, I have to optimize the memory usage of the part of the code with the tests
Could you please check if memory usage is acceptable now?
Well, it seems that it's okay now (the test code takes 114 KB), but I would like to hear opinion of @monadius
It seems strange, that all solutions, except author's one, are invalidated, including that one by monadius. There may be an issue with test suite over-adapted for a certain method, requiring micro-optimizations (generally not positive).
Horosho
This comment has been hidden.
It seems, most solutions got invalidated due to buffer overload. And it's partially due to reference solution, which also takes a lot of memory.
I think you should log this as issue.
Done.
This comment has been hidden.
I've added this and made the tests even harder.
Making tests harder is a bad idea. In my opinion, the upper bound should be reduced to 1010. Your solution times out very often. It is unacceptable. Moreover, it would be a better kata if it were possible to solve it by reading Wikipedia only.
I didn’t quite understand, but what stage of the solution is not from Wikipedia?
This comment has been hidden.
This comment has been hidden.
This comment has been hidden.
No problem, I can add links and make the tests easier
@monadius, could you take a look at the issue above, please?
I closed the issue above because tests seems to be working well now. Feel free to open a new issue if you still think that tests are not well-balanced.
69, 420, 666
You have some good taste, nice
34 has its meaning too ;)
After you reminded, I remembered... Indeed it does :)
This kyu 2 is nothing compared to this :)
Actually, there is a solution for my kata for larger n, maybe I can implement it, but I haven’t figured it out ... yet)
This comment has been hidden.
Yes
im currently using my half-solution from that kata for this kata (my solution is too slow)