How to improve upon this code for finding prime numbers in a given range, using different ways.

ajiten · 07-18-2024, 12:23 AM

I have only in mind profilers, but that too need directions; and if other ways exist, then please tell.
The program finds all prime numbers in a given range.
Intend to make it like a professional code.

Code:

import math
#print('Enter the number till which need find the prime numbers')
n = int(input('Enter the number till which need find the prime numbers : '))
list_prime=[]

for i in range (2,n+1):
    prime = 0
    val = math.ceil(math.sqrt(i))
    print(f'sqrt of {i} is { math.sqrt(i)}, need check till : { val}')
    for j in range (2, val+1):
        print(f'i : {i}, j : {j}')
        if (i % j == 0):
            prime = 0
            break
        else:
            prime = 1
            if j < val:
                continue
            else:
                list_prime.append(i)
        
print(f'list of prime numbers is : {list_prime}')

shruggy · 07-18-2024, 01:24 AM

You can find quite a few ideas when studying examples at Rosetta Code.

schneidz · 07-20-2024, 03:27 PM

ħis iz hwut ī kum up wiħ:

Code:

#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#include <math.h>

int main(int argc, char *argv[])
{
  int i = 5;
  int prīmz[3000] = {2,3};
  int prīmzindex = 2;
  int izprime = 1;

  printf("2\n3\n");
  while(i <= 10000)
  {
      izprime = 1;
      for(int j = 1; prīmz[j] <= (int) sqrt(i); j++)
      {
       if(i % prīmz[j] == 0)
       {
           izprime--;
           break;
       }
      }
      if(izprime == 1)
      {
        prīmz[prīmzindex] = i;
        prīmzindex++;
        printf("%d\n", i);
      }
      if(i % 6 == 5)
      {
          i = i + 2;
      } else {
          i = i + 4;
      }
  }
}

sundialsvcs · 07-22-2024, 06:50 AM

Comments:

(1) The prime flag variable is never used and is therefore unnecessary.

(2) If the code is clear to the unfamiliar reader, and if it can be shown to work in all(!) cases that it will ever actually encounter ... "it's 'professional' enough." Move on to the next one. I've seen aplenty of "very strange code" that worked.

pan64 · 07-22-2024, 07:02 AM

yes, use python linters to improve your code.
use a profiler to check the efficiency of your code.
if you want to go for speed use compiled language instead of python.

ajiten · 07-23-2024, 11:42 PM

Quote:

Originally Posted by sundialsvcs

Comments:

(1) The prime flag variable is never used and is therefore unnecessary.

(2) If the code is clear to the unfamiliar reader, and if it can be shown to work in all(!) cases that it will ever actually encounter ... "it's 'professional' enough." Move on to the next one. I've seen aplenty of "very strange code" that worked.

Yes, the removal of the prime flag variable, made no difference; and was unnecessary.

But, seems that my code is 'strange' too.

NevemTeve · 07-24-2024, 12:08 AM

You can list even primes first, then process odd ones.

pan64 · 07-24-2024, 12:53 AM

Code:

instead of 
for j in range (2, val+1): 
probably 
for j in list_prime

would be faster. That is how it is implemented in post #3.

ajiten · 07-24-2024, 01:00 AM

Quote:

Originally Posted by schneidz

ħis iz hwut ī kum up wiħ:

Code:

#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#include <math.h>

int main(int argc, char *argv[])
{
  int i = 5;
  int prīmz[3000] = {2,3};
  int prīmzindex = 2;
  int izprime = 1;

  printf("2\n3\n");
  while(i <= 10000)
  {
      izprime = 1;
      for(int j = 1; prīmz[j] <= (int) sqrt(i); j++)
      {
       if(i % prīmz[j] == 0)
       {
           izprime--;
           break;
       }
      }
      if(izprime == 1)
      {
        prīmz[prīmzindex] = i;
        prīmzindex++;
        printf("%d\n", i);
      }
      if(i % 6 == 5)
      {
          i = i + 2;
      } else {
          i = i + 4;
      }
  }
}

The code is not in Python, but the optimization made, once a prime number is detected is good.
Say, the first integer that satisfies (i%6==5), is i=5. The next prime number is 7. There is no need to search for (i+2)+2, as it yields 9.
Similarly, second integer that satisfies (i%6==5), is i=11. The next prime number is 13. There is no need to search for (i+2)+2, as it yields 15.
Similarly, third integer that satisfies (i%6==5), is i=17. The next prime number is 19. There is no need to search for (i+2)+2, as it yields 21.
It seems like a theorem, as only (i%6==5), (i%6==5)+2 are primes, while (i%6==5)+4 is an even number.
-------------------------------------------------------------------------------------
Also, if (i%6 !=5), then have options:
(i%6 ==0): this is immaterial, as would be also detected on division by 2, as in 'my code', there would be 'break', to the code flow execution.
(i%6 ==1): 7, 13, 19, 31, 37, 43,... are primes, though 25, 49,... are not
(i%6 ==2): 8, 14, 20, ...
(i%6 ==3): 9, 15, 21, 27, ...
(i%6 ==4): 4, 10, 16, 22, 26,

None, of the above options of the modulo reminders (i.e., those apart from (i%6 ==5)) yields any prime on taking : i+4.
Please tell what is special in choosing i = i +4?

pan64 · 07-24-2024, 01:18 AM

Code:

      if(i % 6 == 5)
      {
          i = i + 2;
      } else {
          i = i + 4;
      }

It is an interesting trick. i is odd, unconditionally, it cannot be even.
i%6 can be therefore 1, 3, 5, nothing else.
i%6 == 3 means i is not a prime, it can be divided by 3, therefore it can be safely skipped. So, the meaning of the code,
if i%6 == 5 then take the next number where i%6 = 1
else i%6 should be equal to 1, and in that case take the next number where i%6 = 5.

kilgoretrout · 07-24-2024, 10:27 AM

A common way is to use the Sieve of Eratosthenes. It's faster than computational methods. See:

https://en.wikipedia.org/wiki/Sieve_of_Eratosthenes

Here's some code I wrote in C a long time ago using this method:

Code:

#include <stdio.h>
#include <stdbool.h>
#include <stdlib.h>


int main()
{
    /* Need long int here. Apparent max size of array is 1/2 of int max.
     * Will segfault if int is used on N values >= than 1/2 int max(1073741824).
     * Using long int instead solves this problem.
     * Also need dynamic memory here(malloc) since stack max is quickly exceeded
     * for larger values of N.
     */
    long N;
    puts("Enter a positive interger greater than 2");
    scanf("%lu", &N);
    printf("You entered %lu\n", N);
    bool *s = malloc(2*N*sizeof(_Bool)); //without 2*N instead of N it segfaults    
    
    //initialize array
    long m;
    for(m=0; m < N; m++)
        s[m] = 1;    
    s[0] = 0;
    s[1] = 0;
    
    for(long i = 0; i < N; i++)
    {
        if(s[i] == 1)
        {
            for(long k = i; k < N; k = k+i)
                s[k+i] = 0;
        }
    }
    
    int count = 0;
    for(long i = 0; i < N; i++)
    {
        if(s[i] == 1){
            printf("%lu  ", i);
            count++;
        }
        
    }
    printf("\n");
    printf("There are %i primes between 0 and %lu.\n", count, N);
    
    free(s);
    
    return 0;
}

The downside of this method is the memory requirements. To give you an idea of the speed of this method, I ran your code and mine finding all the primes between 1 and 1,000,000 and timed the run time.
My code:

Code:

There are 78498 primes between 0 and 1000000.
real    0m3.267s
user    0m0.011s
sys     0m0.000s

Your code:

Code:

real    1m47.136s
user    0m44.747s
sys     0m38.624s

So three seconds versus over a minute and a half. Some of that is the speed of C versus python but most of it is the algorithm.

pan64 · 07-24-2024, 12:48 PM

https://github.com/kimwalisch/primes...f-Eratosthenes
if you are interested.

smallpond · 07-24-2024, 01:57 PM

I keep this python code around for when I need primes. It uses python slices which are very fast. It takes about 0.3s for 2M primes.

Code:

def sieve_for_primes_to(n):
    ''' Returns a table which may be used to test primality '''
    sieve = [True]*n              # set all to prime
    sieve[0::2] = [False]*(n//2)  # clear 0 and evens
    sieve[1] = False              # 1 is not prime
    sieve[2] = True               # 2 is prime
    limit = int(n**0.5) + 1
    # Start at 3 and do odd numbers to sqrt(n)
    for i in range(3,limit,2):
        if sieve[i]:
            nmp = ((n-1)//i)-1    # number of multiples
            sieve[2*i::i] = [False]*nmp  # clear slice of multiples
    return sieve

# example usage
prime = sieve_for_primes(2000000)
if prime[k]:
   print("k is prime")

pan64 · 07-25-2024, 02:27 AM

Quote:

Originally Posted by smallpond

I keep this python code around for when I need primes. It uses python slices which are very fast. It takes about 0.3s for 2M primes.

Wow! I like it.

NevemTeve · 07-28-2024, 09:19 AM

Off: the above code is easy to translate into C, which gives a bit more speed.

Code:

/* primes.c */

#include <math.h>
#include <stdio.h>
#include <stdlib.h>

unsigned char *sieve_for_primes_to(int n)
{
    /* Returns a table which may be used to test primality */
    unsigned char *sieve= malloc(n * sizeof(unsigned char));
    for (int i=0; i<n; i+=2) {
        sieve[i]= 0;           /* set even to non-prime */
        sieve[i+1]= 1;         /* set odd to prime */
    }
    sieve[1] = 0;              /* 1 is not prime */
    sieve[2] = 1;              /* 2 is prime */
    int limit = ceil(sqrt((double)n));
    /* Start at 3 and do odd numbers to sqrt(n) */
    for (int i=3; i<limit; i+=2) {
        if (sieve[i]) {
            for (int j=2*i; j<n; j+=i) {
                sieve[j]= 0;
            }
        }
    }
    return sieve;
}

int main(void)
{
    int n= 2000000;
    unsigned char *primes= sieve_for_primes_to(n);
    for (int i=0; i<n; ++i) {
        if (primes[i]) {
            printf("%d\n", i);
        }
    }
    return 0;
}