Deduplicate repeated `is_prime` functions

[poyea]

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

[srishtik2310]

Can you assign this to me.

[murilo-goncalves]

I will do it!

[VaishnaviJahagirdar3]

Hi! I'm interested in working on this

[Gyan-Singh]

Can I try solve this prob?

[spyboy01]

hey could you please assign it to me .

[paulosgf]

Are there someone working on this fix?

[wellinston123]

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]

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

I have started to work on this issue.

[paulosgf]

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]

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]

@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]

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]

@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]

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]

@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]

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]

@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.

[Manjunadh86]

assign this to me!!!

[DenisOvchinnikov93]

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

[anipaul2]

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

[cwandoff]

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

[poyea]

@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]

@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?

[basketballlegendsgame]

I wanted to learn Python, but it seems to be a difficult language.

[paulosgf]

@rileyawheeler here isn't the right place to address this, but I'll open a brief comment here. Python is one of the more user-friendly languages. C \ C++ is difficult. To start with Python, you can try it in phases where each of them treats one topic through this free project's resource here: https://automatetheboringstuff.com/ You can complement your study with the free tutorials on https://realpython.com/ too. It's excellent! Good luck!

[ngtanthanh]

I used to learn Python, but it seems to be a difficult language.

[stale[bot]]

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]

@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]

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]

Assign this to me.

[Amanrk7]

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

[poyea]

@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]

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]

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

[Casper1012275]

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 https://github.com/TheAlgorithms/Python/issues/5434#issuecomment-1152959838, or unsubscribe https://github.com/notifications/unsubscribe-auth/ATCOCCS3DUXUQW4EGPLFVXLVOS5SBANCNFSM5GIZBEHQ . You are receiving this because you are subscribed to this thread.Message ID: @.***>

[ngiachou]

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 :wink: ).

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

1. 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)).
2. The functions in prime_check.py and primelib.py are not defined as is_prime should we change those too?
3. 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! :beers:

[poyea]

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]

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

[ngiachou]

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]

@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]

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