- #1
necromanzer52
- 12
- 0
Hey. I have to create a program in C++ to calculate the number of prime numbers up to a specified number. I also have to print out the first and last 5, but I'll cross that bridge when I come to it.
I can do this fine with integers, but we have to do it where each slot in an array represents 32 bits. We have to use bitshifting to make each bit a 1 for a prime, and a 0 for a non-prime. It wasn't explained to us very well how we're supposed to do this, and I can't find any useful information on the internet. Here's what I have so far:
#include <iostream>
using namespace std;
#define N 100 // size of sieve used
#define size ((N+31)/32) //32 bits per integer hard coded
int sieve[size]; //declare array of bits
int main ()
{
int i, j, m, product, count;
count = 0;
for (i=0;i<size;i++)
{
sieve = 0xFFFFFFFF;
}
sieve [0] = 0xFFFFFFFC;
for (j=0;j<32;j++)
{
if (sieve[0] & (1 << j) == 1) //find the next prime
{
count++; //count the prime
product = 0;
for (m=2;product<32;m++) // set each multiple of the prime to 0.
{
product = m*j;
sieve[0] &~(1<<product);
}
}
}
cout << count << endl;
return 0;
}
This is just my attempt to count the number of primes in the first 32 numbers, and it just keeps giving an output of 0.
I'm completely lost, and any help would be appreciated.
I can do this fine with integers, but we have to do it where each slot in an array represents 32 bits. We have to use bitshifting to make each bit a 1 for a prime, and a 0 for a non-prime. It wasn't explained to us very well how we're supposed to do this, and I can't find any useful information on the internet. Here's what I have so far:
#include <iostream>
using namespace std;
#define N 100 // size of sieve used
#define size ((N+31)/32) //32 bits per integer hard coded
int sieve[size]; //declare array of bits
int main ()
{
int i, j, m, product, count;
count = 0;
for (i=0;i<size;i++)
{
sieve = 0xFFFFFFFF;
}
sieve [0] = 0xFFFFFFFC;
for (j=0;j<32;j++)
{
if (sieve[0] & (1 << j) == 1) //find the next prime
{
count++; //count the prime
product = 0;
for (m=2;product<32;m++) // set each multiple of the prime to 0.
{
product = m*j;
sieve[0] &~(1<<product);
}
}
}
cout << count << endl;
return 0;
}
This is just my attempt to count the number of primes in the first 32 numbers, and it just keeps giving an output of 0.
I'm completely lost, and any help would be appreciated.