Finding primes from 1 upwards

[henryzz]

Originally Posted by Xyzzy

http://www.troubleshooters.com/codec...imenumbers.htm

this is the sort of program i am after
is there a .exe for his program

[ShiningArcanine]

Originally Posted by bsquared

I'm not familiar with XAND, (exclusive AND?? Wouldn't that always evaluate to 0?) But if you have b = 0101 and want to unset the 0100 then

b &= ~(0100)

works.

I misunderstood what needed to be NOTed. That will work.

As for XAND, that evaluates to 1 if 0 & 0 or 1 & 1 and 0 if 0 & 1 or 1 & 0; In C, the equivalent logical expression is ~(x ^ y).

Originally Posted by axn1

I think you've confused which pattern is to be NOT-ed.

If you want to unset 0100 of the pattern 0101, then you do 0101 & ~(0100)
i.e. 0101 & 1011 = 0001. I am not sure why you are getting wrong results. Neither XAND nor a test for checking if the bit is set is needed here.
EDIT:- Perhaps, you were checking 63rd bit which corresponds to the prime 127?


Don't have access to a C compiler


The purpose of j is not to report primes; it is used to traverse the bitmap. Clearing the j-th bit of the bitmap is equivalent to clearing the integer 2*j+1. The usage of j is to merely reduce some shifts inside the critical inner loop.

I tried your code and it works, although I had to include a semicolon at the end of the declaration and it is a pain to follow. Your code does not need j, as it uses i only once at the beginning and then ceases to use it thereafter. Making those changes produces:

for ( i = num * num >> 1; (i >> 5) < b_num; i += num)
{

	arr[i >> 5] &= ~(0x80000000 >> (i & 0x1F));

}

Here is the improved code. I made a few changes in other locations to eliminate warning messages and make the code more consistent:

/*  prime.c */
/*  Oct 17, 2007. */
/*  <my name was here> */
/*  Program to find prime numbers */
#include <stdio.h>
#include <stdlib.h>

unsigned int blocks (const unsigned int len);
int bin_arr_prime_fill (unsigned int * const arr, const unsigned int len);

int main (void)
{

	unsigned int len, num, bitVal, *arr = NULL;

	printf ("\nFind prime numbers smaller than \n");
	scanf("%i", &len);
			
	if (len < 1)
	{

		return 0;

	}
	
	arr = (unsigned int*)calloc (blocks(len), sizeof(unsigned int));
	
	bin_arr_prime_fill(arr, len);
 
	if (len >= 2)
	{

		printf("Number 2 is a prime number\n");

	}

	/* Loop through Prime Array and Output Primes */
	for ( num = 1; num <= len ; ++arr )
	{

		for ( bitVal = 0x80000000; bitVal > 0 && num <= len; bitVal >>= 1,
num += 2 )
		{
	
			if ((*arr & bitVal) == bitVal)
			{   
	 
				printf("Number %i is a prime number\n", num);
		
			}
	 
		}
	
	}
		
	free(arr - blocks(len));
	
	main();
	
	return 0;
	
}

unsigned int blocks (const unsigned int len)
{

	return ( len % (sizeof(unsigned int) << 4) == 0 ) ?
		(len / (sizeof(unsigned int) << 4)) :
		(len / (sizeof(unsigned int) << 4) + 1);

}

int bin_arr_prime_fill (unsigned int * const arr, const unsigned int len)
{

	unsigned int num, i, b_num = blocks(len);

	for ( num = 0 ; num < b_num ; ++num )
	{
	
		arr[num] = 0xFFFFFFFF;

	}

	arr[0] &= ~0x80000000;

	/* num is the number being checked for primiality */

	for ( num = 3; num * num <= len ; num += 2 )
	{

		if ((arr[num >> 6] & (0x80000000 >> ((num >> 1) & 0x1F))) == 0) 
		{

			continue;

		}
		
		for ( i = num * num >> 1 ; (i >> 5) < b_num ; i += num )
		{

			arr[i >> 5] &= ~(0x80000000 >> (i & 0x1F));

		}

	}
	
	return 0;
	
}

[Jens K Andersen]

Originally Posted by henryzz

http://www.troubleshooters.com/codec...imenumbers.htm
this is the sort of program i am after
is there a .exe for his program

It looks like a poor sieve and silly ideas about how to sieve an interval larger than the ram. I wouldn't bother looking for a .exe or compiling it.
Computing billions of primes from 0 is so easy that it's redone by many people each time the primes are used for something. If you really want a program which just computes primes without doing anything other than writing them then there is a .exe in http://hjem.get2net.dk/jka/math/primeprint.zip. The used sieve is relatively slow and only works to 10^12 but it probably won't take long to create as large a file as you want to use space on.