mirror of https://github.com/cc65/cc65.git
126 lines
2.8 KiB
C
126 lines
2.8 KiB
C
#include <stdio.h>
|
|
#include <stdlib.h>
|
|
|
|
typedef unsigned char byte;
|
|
typedef unsigned short int ushort;
|
|
typedef unsigned long int ulong;
|
|
|
|
#define LIMIT 100000L
|
|
|
|
// BITARRAY
|
|
//
|
|
// My bit-access macros pre-divide by two on the presumption that you'll never
|
|
// try try access both odd and even bits!
|
|
|
|
#define GETBIT(array, bit) (array[bit >> 4] & (1 << ((bit >> 1) & 7)))
|
|
#define SETBIT(array, bit) (array[bit >> 4] |= (1 << ((bit >> 1) & 7)))
|
|
#define CLRBIT(array, bit) (array[bit >> 4] &= ~(1 << ((bit >> 1) & 7)))
|
|
|
|
// RepeatChar
|
|
//
|
|
// Outputs a given character N times
|
|
|
|
void RepeatChar(char c, size_t count)
|
|
{
|
|
while (count--)
|
|
putc(c, stdout);
|
|
}
|
|
|
|
// sqrti
|
|
//
|
|
// Binary search integer square root
|
|
|
|
ushort sqrti(ulong num)
|
|
{
|
|
long i;
|
|
ulong ret = 0;
|
|
|
|
for(i = 15; i >= 0; i--)
|
|
{
|
|
ulong temp = ret | (1L << (ulong)i);
|
|
if(temp * temp <= num)
|
|
{
|
|
ret = temp;
|
|
}
|
|
}
|
|
return ret;
|
|
}
|
|
|
|
// main()
|
|
//
|
|
// CC65 main function receives no parameters
|
|
|
|
int main(void)
|
|
{
|
|
// CC65 cannot mix code and data so we have to declare all variables here in the function prolog
|
|
|
|
ulong iNumber;
|
|
ushort currentFactor;
|
|
ulong numBytesAllocated, rootOfLimit;
|
|
byte *array;
|
|
ulong countOfPrimes;
|
|
|
|
rootOfLimit = sqrti(LIMIT);
|
|
puts("\r\n\r\n");
|
|
RepeatChar('*', 70);
|
|
puts("\r\n** Prime Number Sieve - Dave Plummer 2022 **");
|
|
RepeatChar('*', 70);
|
|
|
|
printf("\r\n\r\nCalculating primes to %ld using a sqrt of %ld...\r\n", LIMIT, rootOfLimit);
|
|
|
|
// Calculate how much memory should be allocated
|
|
|
|
numBytesAllocated = (LIMIT + 15) / 16;
|
|
array = malloc(numBytesAllocated);
|
|
if (!array)
|
|
{
|
|
printf("Unable to allocate %ld bytes for %ld bits\r\n", numBytesAllocated, LIMIT);
|
|
return 0;
|
|
}
|
|
else
|
|
{
|
|
printf("Allocated %ld bytes for %ld slots\r\n", numBytesAllocated, LIMIT);
|
|
|
|
// Preset all the bits to true
|
|
|
|
for (iNumber = 0; iNumber < numBytesAllocated; iNumber++)
|
|
array[iNumber] = 0xFF;
|
|
}
|
|
|
|
// Search for next unmarked factor
|
|
|
|
currentFactor = 3;
|
|
while (currentFactor <= rootOfLimit)
|
|
{
|
|
ulong num, n;
|
|
|
|
for (num = currentFactor; num <= LIMIT; num += 2)
|
|
{
|
|
if (GETBIT(array, num))
|
|
{
|
|
currentFactor = num;
|
|
break;
|
|
}
|
|
}
|
|
|
|
for (n = (ulong) currentFactor * currentFactor; n <= LIMIT; n += currentFactor * 2)
|
|
CLRBIT(array, n);
|
|
|
|
currentFactor += 2;
|
|
}
|
|
|
|
// Display results
|
|
//
|
|
// printf("The following primes were found at or below %ld:\r\n2, ", LIMIT);
|
|
|
|
countOfPrimes = 1;
|
|
for (iNumber = 3; iNumber <= LIMIT; iNumber += 2)
|
|
if (GETBIT(array, iNumber))
|
|
countOfPrimes++;
|
|
|
|
printf("[END: Count = %ld]\r\n", countOfPrimes);
|
|
|
|
free(array);
|
|
return 1;
|
|
}
|