Programming This forum is for all programming questions.
The question does not have to be directly related to Linux and any language is fair game. 
Notices 
Welcome to LinuxQuestions.org, a friendly and active Linux Community.
You are currently viewing LQ as a guest. By joining our community you will have the ability to post topics, receive our newsletter, use the advanced search, subscribe to threads and access many other special features. Registration is quick, simple and absolutely free. Join our community today!
Note that registered members see fewer ads, and ContentLink is completely disabled once you log in.
Are you new to LinuxQuestions.org? Visit the following links:
Site Howto 
Site FAQ 
Sitemap 
Register Now
If you have any problems with the registration process or your account login, please contact us. If you need to reset your password, click here.
Having a problem logging in? Please visit this page to clear all LQrelated cookies.
Get a virtual cloud desktop with the Linux distro that you want in less than five minutes with Shells! With over 10 preinstalled distros to choose from, the worryfree installation life is here! Whether you are a digital nomad or just looking for flexibility, Shells can put your Linux machine on the device that you want to use.
Exclusive for LQ members, get up to 45% off per month. Click here for more info.


07182024, 12:23 AM

#1

Member
Registered: Jun 2023
Posts: 380
Rep:

How to improve upon this code for finding prime numbers in a given range, using different ways.
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}')
Last edited by ajiten; 07182024 at 12:28 AM.



07182024, 01:24 AM

#2

Senior Member
Registered: Mar 2020
Posts: 3,706
Rep:

You can find quite a few ideas when studying examples at Rosetta Code.
Last edited by shruggy; 07182024 at 01:28 AM.



07202024, 03:27 PM

#3

LQ Guru
Registered: May 2005
Location: boston, usa
Distribution: fedora35
Posts: 5,325

ħ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;
}
}
}
Last edited by schneidz; 07202024 at 03:31 PM.


1 members found this post helpful.

07222024, 06:50 AM

#4

LQ Guru
Registered: Feb 2004
Location: SE Tennessee, USA
Distribution: Gentoo, LFS
Posts: 10,820

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.


1 members found this post helpful.

07222024, 07:02 AM

#5

LQ Addict
Registered: Mar 2012
Location: Hungary
Distribution: debian/ubuntu/suse ...
Posts: 22,636

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.



07232024, 11:42 PM

#6

Member
Registered: Jun 2023
Posts: 380
Original Poster
Rep:

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.



07242024, 12:08 AM

#7

Senior Member
Registered: Oct 2011
Location: Budapest
Distribution: Debian/GNU/Linux, AIX
Posts: 4,923

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



07242024, 12:53 AM

#8

LQ Addict
Registered: Mar 2012
Location: Hungary
Distribution: debian/ubuntu/suse ...
Posts: 22,636

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.



07242024, 01:00 AM

#9

Member
Registered: Jun 2023
Posts: 380
Original Poster
Rep:

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?



07242024, 01:18 AM

#10

LQ Addict
Registered: Mar 2012
Location: Hungary
Distribution: debian/ubuntu/suse ...
Posts: 22,636

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.


2 members found this post helpful.

07242024, 10:27 AM

#11

Senior Member
Registered: Oct 2003
Posts: 3,000

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.



07242024, 12:48 PM

#12

LQ Addict
Registered: Mar 2012
Location: Hungary
Distribution: debian/ubuntu/suse ...
Posts: 22,636




07242024, 01:57 PM

#13

Senior Member
Registered: Feb 2011
Location: Massachusetts, USA
Distribution: Fedora
Posts: 4,196

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 = ((n1)//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")



07252024, 02:27 AM

#14

LQ Addict
Registered: Mar 2012
Location: Hungary
Distribution: debian/ubuntu/suse ...
Posts: 22,636

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.



07282024, 09:19 AM

#15

Senior Member
Registered: Oct 2011
Location: Budapest
Distribution: Debian/GNU/Linux, AIX
Posts: 4,923

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 nonprime */
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;
}


2 members found this post helpful.

All times are GMT 5. The time now is 02:13 AM.

LinuxQuestions.org is looking for people interested in writing
Editorials, Articles, Reviews, and more. If you'd like to contribute
content, let us know.

Latest Threads
LQ News

