i am a new person pliiiiiz help :( :( :(

Let's talk about algorithms!

Moderator: Board moderators

Post Reply
User avatar
Riyad
Experienced poster
Posts: 131
Joined: Thu Aug 14, 2003 10:23 pm
Location: BUET
Contact:

i am a new person pliiiiiz help :( :( :(

Post by Riyad » Sun Aug 31, 2003 5:16 pm

i am a new person in acm . i dont have a code to generate prime no efficiently . so i came to the "algorithm" part of the acm electronic board . i came across two algorithm of generating prime no . but i dont understand any of them . :cry: :cry: :cry: :cry: :cry: :cry:

i wil lbe very great ful if u tell me how to use the algorithm . here are the two algorithms:-

Code: Select all

#include<stdlib.h>
#include<malloc.h>

#define isprime(f,x) (*(f+(x)/16)&(1<<(((x)%16L)/2)))
#define setprime(f,x) *(f+(x)/16)|=1<<(((x)%16L)/2)

void main()
{
unsigned char *field=NULL,*zzz;
unsigned long teste=1,max,mom,count,alloc;
int d;
max=20010000L;

while(field==NULL)
zzz=field=(unsigned char*) malloc(alloc=(((max-=10000L)>>4)+1L));

for (count=0;count<alloc;count++)
*zzz++ = 0x00;

while((teste+=2)<max)
if(!isprime(field,teste))
for(mom=3L*teste;mom<max;mom+=teste<<1)
setprime(field,mom);
	if(isprime(field,3)==1)
/*now you can cll the module isprime to check any positive integer 
either prime or not; 
syntax: 
isprime(field,integer); 

if the module return 0 the integer will be prime 
else not prime. 

you can check upto 20000000 within a while 
*/ 

free (field); 
}

/*MY QUESTION*/

what should i use as a parameter in place of "field" is calling the function 
isPrime(field,integer). that means if i want to calculate the primality of the number 100010041, how should i  call the function isPrime(field?????,100010041)?????????????????????








/*********SIEVE*********/



#define MAXSIEVE 100000000 // All prime numbers up to this 
#define MAXSIEVEHALF (MAXSIEVE/2) 
#define MAXSQRT 5000 // sqrt(MAXSIEVE)/2 
char a[MAXSIEVE/16+2]; 
#define isprime(n) (a[(n)>>4]&(1<<(((n)>>1)&7))) // Works when n is odd 

int i,j; 
memset(a,255,sizeof(a)); 
a[0]=0xFE; 
for(i=1;i<MAXSQRT;i++) 
if (a[i>>3]&(1<<(i&7))) 
for(j=i+i+i+1;j<MAXSIEVEHALF;j+=i+i+1) 
a[j>>3]&=~(1<<(j&7)); 
sorry for my being too stupid to paste a code that i dont even under stand
pliiiiiiiiiiiiiiiiiz help me
Bye
Riyad
HOLD ME NOW ,, I AM 6 FEET FROM THE EDGE AND I AM THINKIN.. MAY BE SIX FEET IS SO FAR DOWN

User avatar
little joey
Guru
Posts: 1080
Joined: Thu Dec 19, 2002 7:37 pm

Post by little joey » Sun Aug 31, 2003 6:02 pm

Well, my advise is: don't try to understand them. Both are written by people who try to look smart, but realy don't know how to code properly.
The first is probably copied and edited from some website and potentialy erronious. The second is better, but could lead to serious trouble if you don't use it properly [Edit: I'll take that last statement back on second thought].

If you're new to the field, read up on primality testing and prime sieves, you will understand that pretty quick and be able to write your own routines.
The vast majority of problems on this site dealing with prime numbers can be solved using clear coded, simple primality tests. The few that require goofy code like the above, are better left alone, and can be probably solved using better but more complex algorithms.

It's only my opinion, take it or leave it.
Last edited by little joey on Sun Aug 31, 2003 8:35 pm, edited 1 time in total.

User avatar
Riyad
Experienced poster
Posts: 131
Joined: Thu Aug 14, 2003 10:23 pm
Location: BUET
Contact:

thanx for u r advice bosssssssssss

Post by Riyad » Sun Aug 31, 2003 8:04 pm

this is the first time i think i have got a proper advice and i like it . u r right , i dont need to understand this thingssssssssssss. ok little joey need a little help , i guess u ll help me . where can i get the algorithm "sieve"--->the main thing not pseudo code , the theory i mean to say . i need the web site address where i can get "sieve" the theory.

thanx once again for the advice little joey.
Bye
Riyad
HOLD ME NOW ,, I AM 6 FEET FROM THE EDGE AND I AM THINKIN.. MAY BE SIX FEET IS SO FAR DOWN

Larry
Guru
Posts: 647
Joined: Wed Jun 26, 2002 10:12 pm
Location: Hong Kong and New York City
Contact:

Post by Larry » Sun Aug 31, 2003 8:15 pm

If I remember correctly, the latter's written by Yarin, who I wouldn't say don't know how to code properly. =P

You should search for it on google, it returns so many hits that you shouldnt have trouble finding it.. =)

User avatar
rakeb
New poster
Posts: 42
Joined: Fri Aug 30, 2002 2:51 pm
Location: France

Post by rakeb » Sun Aug 31, 2003 8:21 pm

i can show u how sieve of eratosthenes works but not ur code. cause it looks very unusual.

the sieve of eratosthenes is used to find all prime not exceeding a specified positive integer. let us take our limit is 100

take a bool type global array prime[limit+1]

first set prime[1]=1 // 1 indicates composit & 0 indicates prime

now first the integers that are divisible by 2, other than 2 are deleted (i.e. set to 1)
i.e
for 2 ---> prime[4] prime[6] prime[8] prime[10] prime[12] ................ upto prime[100] are set to 1

since 3 is the first integer greater than 2 is left (i.e. not deleted), all the integers that are divisible by 3, other than 3 are deleted
i.e
for 3 ---> prime[6] prime[9] prime[12] prime[15] prime[18] ................ upto prime[100] are set to 1

since 5 is the next integer left (i.e. not deleted), all the integers that are divisible by 5, other than 5 are deleted
i.e
for 5 ---> prime[10] prime[15] prime[20] prime[25] prime[30] ................ upto prime[100] are set to 1

since 7 is the next integer left (i.e. not deleted), all the integers that are divisible by 7, other than 7 are deleted
i.e
for 7 ---> prime[14] prime[21] prime[28] prime[35] prime[42] ................ upto prime[100] are set to 1

since all the composit integers not exceding 100 are divisable by 2,3,5 or 7 (all prime numbers <=sqrt(100)), all remaining integers in the prime[] array (i.e. which are not deleted i.e. for which x, prime[x]==0 ) are prime.

it can be easily implemented by two for loops. also the code can be speeded up little bit by little bit of thinking.

hope this can help
Rakeb

User avatar
little joey
Guru
Posts: 1080
Joined: Thu Dec 19, 2002 7:37 pm

Post by little joey » Sun Aug 31, 2003 9:03 pm

Larry: Oops, don't want to get into the clinch with Jimmy. :oops:
I already editted my previous message before reading your comment. I must admit, it's probably the fastest way to code a sieve there exists. Sorry.

Riyad: read rakeb's posting. It explains it all.
Last edited by little joey on Mon Sep 01, 2003 3:46 am, edited 1 time in total.

Julien Cornebise
Experienced poster
Posts: 145
Joined: Sat Feb 23, 2002 2:00 am
Location: Paris, France
Contact:

Post by Julien Cornebise » Sun Aug 31, 2003 10:11 pm

Hi
For all mathematics question, I strongly advise you to refer to wolfram's (in my opinion) excelent website !
http://mathworld.wolfram.com
To me, such a website is sometimes very close to paradise : an unbelievable knowledge at hand !
For your very question :
http://mathworld.wolfram.com/PrimeNumber.html
http://mathworld.wolfram.com/SieveofEratosthenes.html

Little Joey : surprisingly, 42 is not a prime number ... though it's the first number by order of importance ! (In french, prime number = "nombre premier", the first number = "le premier nombre") :wink: (sorry, off topic, but I couldn't resist ) :)

User avatar
Riyad
Experienced poster
Posts: 131
Joined: Thu Aug 14, 2003 10:23 pm
Location: BUET
Contact:

thanx all the people

Post by Riyad » Tue Sep 02, 2003 2:49 am

u people are the best . thanx for u r help . i understood sieve , special thanx to rakeb and little joey . dont want to get into any contradiction , all of u are good and better than me .
thanx once again
Bye
Riyad

i coded a sieve which is working perfectly :D
HOLD ME NOW ,, I AM 6 FEET FROM THE EDGE AND I AM THINKIN.. MAY BE SIX FEET IS SO FAR DOWN

xbeanx
Experienced poster
Posts: 114
Joined: Wed Jul 30, 2003 10:30 pm
Location: Newfoundland, Canada (St. John's)

Post by xbeanx » Fri Sep 05, 2003 10:36 pm

Wolfram's MATHWORLD is probably the best resource out there for math help. Whenever I need any information about anything math I always visit there first.

Post Reply

Return to “Algorithms”