Deduplicate repeated `is_prime` functions #5434

poyea · 2021-10-19T10:26:58Z

We have a lot of is_prime (or similar) functions: https://github.com/TheAlgorithms/Python/search?p=4&q=is_prime, https://github.com/TheAlgorithms/Python/search?q=isPrime, data_structures/hashing/number_theory/prime_numbers, etc. Shall we use one common function for that exactly identical is_prime calculation (which takes O(sqrt(n)))?

Candidates include:

The text was updated successfully, but these errors were encountered:

srishtik2310 · 2021-10-19T14:33:01Z

Can you assign this to me.

murilo-goncalves · 2021-10-20T18:50:15Z

I will do it!

VaishnaviJahagirdar3 · 2021-10-28T10:21:12Z

Hi! I'm interested in working on this

Gyan-Singh · 2021-10-28T18:13:10Z

Can I try solve this prob?

paulosgf · 2021-12-06T17:26:34Z

Are there someone working on this fix?

wellinston123 · 2021-12-08T09:27:13Z

Write a function that takes a list sorted in non-decreasing order and deletes any duplicate nodes from the list. The list should only be traversed once.
For example if the linked list is 11->11->11->21->43->43->60 then removeDuplicates() should convert the list to 11->21->43->60. Algorithm:
Traverse the list from the head (or start) node. While traversing, compare each node with its next node. If the data of the next node is the same as the current node then delete the next node. Before we delete a node, we need to store the next pointer of the node.

paulosgf · 2021-12-08T11:49:17Z

I'd like do it. Is there anyone working on it?

I have started to work on this issue.

paulosgf · 2021-12-10T13:16:16Z

We have a lot of is_prime (or similar) functions: https://github.com/TheAlgorithms/Python/search?p=4&q=is_prime, https://github.com/TheAlgorithms/Python/search?q=isPrime, data_structures/hashing/number_theory/prime_numbers, etc. Shall we use one common function for that exactly identical is_prime calculation (which takes O(sqrt(n)))?

Candidates include:

maths/prime_check

maths/primelib

Hi @poyea!
I think that isn't not too simple to only change is_prime() similar functions by one patter as prime_check() function, because
while, for example, maths.prime_check.prime_check() is defined with def prime_check(number: int) -> bool , maths.miller_rabin.py.is_prime() is defined as def is_prime(n, prec=1000)
I sugests to only change the maths.miller_rabin.py.is_prime() name to something more compatible with his context, as big_num_is_prime().
What do you think?

nnamansingh · 2021-12-13T08:08:43Z

Do the sorting first and then make it a set as the set will return unique values and by this all the duplicates will be removed

paulosgf · 2021-12-14T19:05:51Z

@poyea,

I have other question: some problems in projecteuler folder seens to be resolved already. Some require a function like is_prime(), to determine if it's prime or not and this function is ready to work. Shouldn't they be empty?
See project_euler/problem_010/sol1.py

poyea · 2021-12-16T09:11:33Z

We have a lot of is_prime (or similar) functions: https://github.com/TheAlgorithms/Python/search?p=4&q=is_prime, https://github.com/TheAlgorithms/Python/search?q=isPrime, data_structures/hashing/number_theory/prime_numbers, etc. Shall we use one common function for that exactly identical is_prime calculation (which takes O(sqrt(n)))?
Candidates include:

maths/prime_check

maths/primelib

Hi @poyea! I think that isn't not too simple to only change is_prime() similar functions by one patter as prime_check() function, because while, for example, maths.prime_check.prime_check() is defined with def prime_check(number: int) -> bool , maths.miller_rabin.py.is_prime() is defined as def is_prime(n, prec=1000) I sugests to only change the maths.miller_rabin.py.is_prime() name to something more compatible with his context, as big_num_is_prime(). What do you think?

The is_prime in maths.miller_rabin.py could be omitted (maybe rename it to miller_rabin or similar), as it should be a standalone algorithm.

poyea · 2021-12-16T09:15:05Z

@poyea,

I have other question: some problems in projecteuler folder seens to be resolved already. Some require a function like is_prime(), to determine if it's prime or not and this function is ready to work. Shouldn't they be empty? See project_euler/problem_010/sol1.py

I would say yes, but this may be our second priority because project_euler is a folder of solutions, and we may want them to be self-contained, in some sense. The goal is to replace those repetitively appeared is_prime in other main algorithm files. And make it clear enough for others to use it first.

Maybe we can make a list of these is_prime instances first and decide whether we should change them (at all).

paulosgf · 2021-12-16T18:20:14Z

We have a lot of is_prime (or similar) functions: https://github.com/TheAlgorithms/Python/search?p=4&q=is_prime, https://github.com/TheAlgorithms/Python/search?q=isPrime, data_structures/hashing/number_theory/prime_numbers, etc. Shall we use one common function for that exactly identical is_prime calculation (which takes O(sqrt(n)))?
Candidates include:

maths/prime_check

maths/primelib

Hi @poyea! I think that isn't not too simple to only change is_prime() similar functions by one patter as prime_check() function, because while, for example, maths.prime_check.prime_check() is defined with def prime_check(number: int) -> bool , maths.miller_rabin.py.is_prime() is defined as def is_prime(n, prec=1000) I sugests to only change the maths.miller_rabin.py.is_prime() name to something more compatible with his context, as big_num_is_prime(). What do you think?

The is_prime in maths.miller_rabin.py could be omitted (maybe rename it to miller_rabin or similar), as it should be a standalone algorithm.

I left as big_num_is_prime because his usage is for "This is a probabilistic check to test primality, useful for big numbers".

paulosgf · 2021-12-16T18:20:53Z

@poyea,
I have other question: some problems in projecteuler folder seens to be resolved already. Some require a function like is_prime(), to determine if it's prime or not and this function is ready to work. Shouldn't they be empty? See project_euler/problem_010/sol1.py

I would say yes, but this may be our second priority because project_euler is a folder of solutions, and we may want them to be self-contained, in some sense. The goal is to replace those repetitively appeared is_prime in other main algorithm files. And make it clear enough for others to use it first.

Maybe we can make a list of these is_prime instances first and decide whether we should change them (at all).

I'll do it.

paulosgf · 2021-12-22T18:54:09Z

We have a lot of is_prime (or similar) functions: https://github.com/TheAlgorithms/Python/search?p=4&q=is_prime, https://github.com/TheAlgorithms/Python/search?q=isPrime, data_structures/hashing/number_theory/prime_numbers, etc. Shall we use one common function for that exactly identical is_prime calculation (which takes O(sqrt(n)))?
Candidates include:

maths/prime_check

maths/primelib

Hi @poyea! I think that isn't not too simple to only change is_prime() similar functions by one patter as prime_check() function, because while, for example, maths.prime_check.prime_check() is defined with def prime_check(number: int) -> bool , maths.miller_rabin.py.is_prime() is defined as def is_prime(n, prec=1000) I sugests to only change the maths.miller_rabin.py.is_prime() name to something more compatible with his context, as big_num_is_prime(). What do you think?

The is_prime in maths.miller_rabin.py could be omitted (maybe rename it to miller_rabin or similar), as it should be a standalone algorithm.

I left as big_num_is_prime because his usage is for "This is a probabilistic check to test primality, useful for big numbers".

@poyea,

These are the occurrencies of repeated isprime() like functions found on main libraries of whole project:

maths.primelib.isPrime()
Function to determine if a number is prime or not. This function is just used on his own library of functions to handle with prime numbers and his logic is different of maths.prime_check.prime_check(). prime_check() deals with negative numbers and float point exceptions as opposed to isPrime() and, thus, i think it must be preferred.

ciphers.rabin_miller.isPrime()
Function to determine if a small number is prime or not. Same case as before: it's just used on his own library of functions to handle with prime numbers and dont treat float point exceptions. Renamed to low_num_is_prime().

data_structures.hashing.number_theory.prime_numbers.py
Has 2 functions to perform Hashing operations with prime numbers and i guess it don't interfere with the other prime functions. Unfortunately it don't be documented. Maybe changing his filename?

paulosgf · 2021-12-22T18:57:46Z

@poyea,
I have other question: some problems in projecteuler folder seens to be resolved already. Some require a function like is_prime(), to determine if it's prime or not and this function is ready to work. Shouldn't they be empty? See project_euler/problem_010/sol1.py

I would say yes, but this may be our second priority because project_euler is a folder of solutions, and we may want them to be self-contained, in some sense. The goal is to replace those repetitively appeared is_prime in other main algorithm files. And make it clear enough for others to use it first.
Maybe we can make a list of these is_prime instances first and decide whether we should change them (at all).

I'll do it.

@poyea,

This is a list from Project Euler with isprime() like functions on his solutions:

project_euler.problem_007.sol1.is_prime()
project_euler.problem_010.sol1.is_prime()
project_euler.problem_010.sol2.is_prime()
project_euler.problem_027.sol1.is_prime()
project_euler.problem_035.sol1.is_prime()
project_euler.problem_041.sol1.is_prime()
project_euler.problem_046.sol1.is_prime()
project_euler.problem_049.sol1.is_prime()
project_euler.problem_003.sol1.isPrime()
project_euler.problem_007.sol2.isprime()
project_euler.problem_058.sol1.isPrime()
project_euler.problem_007.sol3.prime_check()

It's to register for later decision.

* Update ciphers.rabin_miller.py maths.miller_rabin.py

Manjunadh86 · 2022-01-05T02:54:16Z

assign this to me!!!

DenisOvchinnikov93 · 2022-01-12T00:36:23Z

I would also like to help, assign me to this please.

anipaul2 · 2022-01-13T11:57:06Z

Assign me to this, please. I would love to help.

cwandoff · 2022-01-21T19:43:03Z

I would also love to help with this! Please assign this to me.

poyea · 2022-01-27T02:08:44Z

@poyea,
I have other question: some problems in projecteuler folder seens to be resolved already. Some require a function like is_prime(), to determine if it's prime or not and this function is ready to work. Shouldn't they be empty? See project_euler/problem_010/sol1.py

I would say yes, but this may be our second priority because project_euler is a folder of solutions, and we may want them to be self-contained, in some sense. The goal is to replace those repetitively appeared is_prime in other main algorithm files. And make it clear enough for others to use it first.
Maybe we can make a list of these is_prime instances first and decide whether we should change them (at all).

I'll do it.

@poyea,

This is a list from Project Euler with isprime() like functions on his solutions:
project_euler.problem_007.sol1.is_prime()
project_euler.problem_010.sol1.is_prime()
project_euler.problem_010.sol2.is_prime()
project_euler.problem_027.sol1.is_prime()
project_euler.problem_035.sol1.is_prime()
project_euler.problem_041.sol1.is_prime()
project_euler.problem_046.sol1.is_prime()
project_euler.problem_049.sol1.is_prime()
project_euler.problem_003.sol1.isPrime()
project_euler.problem_007.sol2.isprime()
project_euler.problem_058.sol1.isPrime()
project_euler.problem_007.sol3.prime_check()
It's to register for later decision.

Perhaps we can change those isPrime to is_prime (as a first step). It would be easier if we want to unify them in the future. The act of unifying them needs a little more thought, as in that case, people need the whole source to run ine single file.

paulosgf · 2022-02-03T18:36:27Z

@poyea, I'm trying to fix the last PR, but a pre-commit hook 'Validate filenames' is preventing me due to hyphens found on filenames, like these venv/lib/python3.8/site-packages/*, even defining the variable SKIP=validate-filenames, to skip this specific hook.
Can I remove this rule from the hooks file, given that this path is always found on commits?

* Fixes (#5434) * Update ciphers.rabin_miller.py maths.miller_rabin.py * Fixing ERROR maths/miller_rabin.py - ModuleNotFoundError and changing project_euler's isPrime to is_prime function names * Update sol1.py * fix: try to change to list * fix pre-commit * fix capital letters * Update miller_rabin.py * Update rabin_miller.py Co-authored-by: John Law <[email protected]>

stale · 2022-04-25T13:41:34Z

This issue has been automatically marked as stale because it has not had recent activity. It will be closed if no further activity occurs. Thank you for your contributions.

paulosgf · 2022-04-25T15:36:45Z

@poyea,

And these issues? We'll be working on them?

These are the occurrences of repeated isprime() like functions found on main libraries of the whole project:

maths.primelib.isPrime()
Function to determine if a number is prime or not. This function is just used on his own library of functions to handle prime numbers and his logic is different of maths.prime_check.prime_check(). prime_check() deals with negative numbers and floating point exceptions as opposed to isPrime() and, thus, i think it must be preferred.

data_structures.hashing.number_theory.prime_numbers.py
Has 2 functions to perform Hashing operations with prime numbers and I guess it doesn't interfere with the other prime functions. Unfortunately, it doesn't be documented. Maybe changing his filename?

AK16092003 · 2022-04-25T16:18:23Z

is_prime function to check whether a given number is prime using O(sqrt N) algorithm

def is_prime(n):

    try:
        n = int(n)
    except:
        print("Not an integer input")
        print("Sorry ! Prime Number checking can be done only on integers")
        return
    
    if n <= 1:
        return False

    for i in range(2,int(n**0.5)+1):
        if n%i == 0:
            return False
    return True

ishwerdutt · 2022-05-18T07:47:05Z

Assign this to me.

Amanrk7 · 2022-06-11T16:27:23Z

Is this problem has been solved ? or i will love to solve this.

poyea · 2022-06-11T20:41:02Z

@Amanrk7 I think the goal here is to make them uniform in function calls and implementations (as opposed to originally make them shared). In this way, every file of code is self-contained and easier to follow.

It would be helpful if you could figure out where those functions are, and how they are implemented - then make those functions 1.) use is_prime function name 2.) see if they are sqrt(N) implementations

paulosgf · 2022-06-12T00:36:35Z

Is this problem has been solved ? or i will love to solve this.

Hi @Amanrk7 ! Feel free to work on this issue. I'll go to get some topics other than first-timers now.
And thank you @poyea for your valuable help!

saidhanunjaynaidu · 2022-06-12T09:29:47Z

give me some sort of problems like this i will show you the output

Casper1012275 · 2022-06-12T09:50:59Z

Please solve this problem

…

On Sat, 11 Jun 2022, 18:32 Aman RK, ***@***.***> wrote: Is this problem has been solved ? or i will love to solve this. — Reply to this email directly, view it on GitHub <#5434 (comment)>, or unsubscribe <https://github.com/notifications/unsubscribe-auth/ATCOCCS3DUXUQW4EGPLFVXLVOS5SBANCNFSM5GIZBEHQ> . You are receiving this because you are subscribed to this thread.Message ID: ***@***.***>

ngiachou · 2022-07-03T00:00:44Z

Hi everyone! So I was searching for a good-first-issue to start contributing to the open source community, and since I have a PhD in Theoretical Computer Science, The Algorithms looks like the best place for me (python is also my favorite programming language 😉 ).

So I was reading all these comments here and did some digging in the source code and I have the following.

For the algorithm in data_structures/hashing/number_theory/prime_numbers.py I think we could refactor it to is_prime and change the algorithm to be O(sqrt(n)).
The functions in prime_check.py and primelib.py are not defined as is_prime should we change those too?
Finally, I stumbled upon a duplicate of Eratosthenes' sieve in sieve_of_eratosthenes.py and prime_sieve_eratosthenes.py should these two get merged? Is this a matter of another issue? I did some search in issues but did not find anything related.

I could do all these changes if no one else has done anything.

Cheers to all of ya! 🍻

poyea · 2022-07-03T16:25:57Z

Hey @elpaxoudis! For 1 & 2, yes, and these can be done altogether in this issue. It would be of help if you could check also other algorithms and files in this repository which define a is_prime function or alike.

For 3, I agree that one of them is a duplicate. Let's handle it in a different issue (or without an issue because it's straightforward in terms of scale of change). We can merge all the test cases / comments, while preserving one clearer version.

poyea · 2022-07-11T14:38:14Z

The next item would be to check against the project_euler files. Afterwards we can close this issue

ngiachou · 2022-07-13T03:07:26Z

Great! Thank you for merging!

So for the Euler files I was thinking of keeping one implementation which will be O(sqrt(n)) to be optimal and using that for all solutions that need primality checking. What do you think @poyea ? Additionally, I'd like to add doctests too.

poyea · 2022-07-18T16:31:28Z

@elpaxoudis That sounds good to me 😃 - unless there's some weird specifications in the problem / custom implementation (say the author wrote a Sieve-like approach) which I'm sure it's rare. Doctests / test cases are always welcome!

Nidhi2003 · 2022-07-25T10:14:26Z

Please assign this to me. I would love to solve this problem.

yndue736 · 2022-08-02T10:56:07Z

This is very similar problem which I am still facing here on the website you can see here and kindly help me about it I hope it will be a suitable choice.

maheshsv · 2022-08-10T09:31:10Z

CAn i work on this issue please

dharuag · 2022-08-10T10:33:12Z

i nknow id problenn slot id ba top ell care full

…

On Wed, Aug 10, 2022 at 3:06 PM Mahesh SV ***@***.***> wrote: CAn i work on this issue please — Reply to this email directly, view it on GitHub <#5434 (comment)>, or unsubscribe <https://github.com/notifications/unsubscribe-auth/ASOPK5AQKOK2ZQFCH3I2ULTVYNZZXANCNFSM5GIZBEHQ> . You are receiving this because you are subscribed to this thread.Message ID: ***@***.***>

shrutiiivij · 2022-08-25T14:13:27Z

if we are working on a list than we have sort it otherwise if we gave a limited amount of number than there is no need to do this we can just apply 2 nested loop it can easily give us the required output
thank u

mahi072 · 2022-09-09T15:18:12Z

Hi I would like to work on this issue, Please assign this to me, if its still open.

* fixes #5434 * fixes broken solution * removes assert * removes assert * Apply suggestions from code review Co-authored-by: John Law <[email protected]> * Update project_euler/problem_003/sol1.py Co-authored-by: John Law <[email protected]>

poyea self-assigned this Oct 19, 2021

poyea added good first issue help wanted labels Oct 19, 2021

murilo-goncalves mentioned this issue Oct 20, 2021

Fix: deduplicated "is_prime" functions #5488

Closed

14 tasks

poyea mentioned this issue Oct 22, 2021

Add doctests to prime_check function #5503

Merged

14 tasks

This comment has been minimized.

Sign in to view

paulosgf added a commit to paulosgf/Python that referenced this issue Dec 29, 2021

Fixes (TheAlgorithms#5434)

eacca6b

* Update ciphers.rabin_miller.py maths.miller_rabin.py

paulosgf mentioned this issue Jan 5, 2022

Remove duplicate is_prime related functions #5892

Merged

14 tasks

stale bot added the stale Used to mark an issue or pull request stale. label Apr 25, 2022

stale bot removed the stale Used to mark an issue or pull request stale. label Apr 25, 2022

ngiachou mentioned this issue Jul 4, 2022

Unify primality checking #6228

Merged

14 tasks

poyea closed this as completed in #6228 Jul 11, 2022

poyea reopened this Jul 11, 2022

ngiachou added a commit to ngiachou/TheAlgorithmsPython that referenced this issue Jul 19, 2022

fixes TheAlgorithms#5434

1fbf132

poyea mentioned this issue Jul 20, 2022

Unify O(sqrt(N)) is_prime functions under project_euler #6258

Merged

14 tasks

poyea closed this as completed in #6258 Sep 14, 2022

Deduplicate repeated is_prime functions #5434

Deduplicate repeated is_prime functions #5434

Comments

poyea commented Oct 19, 2021 • edited Loading

srishtik2310 commented Oct 19, 2021

murilo-goncalves commented Oct 20, 2021

VaishnaviJahagirdar3 commented Oct 28, 2021

Gyan-Singh commented Oct 28, 2021

This comment has been minimized.

paulosgf commented Dec 6, 2021

wellinston123 commented Dec 8, 2021

paulosgf commented Dec 8, 2021

paulosgf commented Dec 10, 2021

nnamansingh commented Dec 13, 2021

paulosgf commented Dec 14, 2021 • edited Loading

poyea commented Dec 16, 2021

poyea commented Dec 16, 2021 • edited Loading

paulosgf commented Dec 16, 2021

paulosgf commented Dec 16, 2021

paulosgf commented Dec 22, 2021

paulosgf commented Dec 22, 2021

Manjunadh86 commented Jan 5, 2022

DenisOvchinnikov93 commented Jan 12, 2022

anipaul2 commented Jan 13, 2022

cwandoff commented Jan 21, 2022

poyea commented Jan 27, 2022

paulosgf commented Feb 3, 2022 • edited Loading

stale bot commented Apr 25, 2022

paulosgf commented Apr 25, 2022

AK16092003 commented Apr 25, 2022

ishwerdutt commented May 18, 2022 • edited Loading

Amanrk7 commented Jun 11, 2022

poyea commented Jun 11, 2022

paulosgf commented Jun 12, 2022

saidhanunjaynaidu commented Jun 12, 2022

Casper1012275 commented Jun 12, 2022 via email

ngiachou commented Jul 3, 2022

poyea commented Jul 3, 2022

poyea commented Jul 11, 2022

ngiachou commented Jul 13, 2022

poyea commented Jul 18, 2022

Nidhi2003 commented Jul 25, 2022

yndue736 commented Aug 2, 2022

maheshsv commented Aug 10, 2022

dharuag commented Aug 10, 2022 via email

shrutiiivij commented Aug 25, 2022

mahi072 commented Sep 9, 2022

Deduplicate repeated `is_prime` functions #5434

Deduplicate repeated `is_prime` functions #5434

poyea commented Oct 19, 2021 •

edited

Loading

paulosgf commented Dec 14, 2021 •

edited

Loading

poyea commented Dec 16, 2021 •

edited

Loading

paulosgf commented Feb 3, 2022 •

edited

Loading

ishwerdutt commented May 18, 2022 •

edited

Loading