/prog/ I'm very deeply stressed at the moment. I have an assignment due tomorrow morning, a prime number algorithm. I know I screwed it up badly, and I'm not even sure if I am on the right track. If there are any capable c++ programmers on /prog/ right now, think you could lend a gal a hand?
Here is a copy of my current code:
#include <iostream>
using namespace std;
int main()
{
int s;
int p;
long PrimeStatus[100001];
PrimeStatus[s] = 1;
long MAX_PRIME_CHECK = 100000;
for(int s = 1; s < MAX_PRIME_CHECK; s++)
{
if(p > 2)
{
PrimeStatus[p] = 1;
return 0;
}
Thank you. I did notice that. Here is a slightly updated version of the code. While it still does not produce the desired outfit, it is a step up from what it was before hand. I am not exactly sure if I understand exactly where you are coming from with the not initializing PrimeStatus.
#include <iostream>
using namespace std;
int main()
{
long PrimeStatus[100001];
long MAX_PRIME_CHECK = 100000;
for(int s = 1; s < MAX_PRIME_CHECK; s++)
{
if(s > 2)
{
PrimeStatus[s] == 0;
return 0;
}
Despite the utter lack of general maturity amongst most of us, at least be somewhat subtle about it. Also, could very well do that with a simple string if you want to be that blunt.
Let a prime number be a number that has no factors aside from one and itself.
A number only has factors that complement eachother, meaning they come in pairs. Thus, you only need to look for factors prior to n / 2.
I'm not exactly sure what you mean by a "prime number algorithm," if you mean it determines a number that's prime or if it generates prime numbers, either of these can be achieved through the use of a prime number function.
bool isPrime(int n) {
bool is = true;
for (int c = 2; c <= (n / 2); c++) { // lul sepples
if ((n % c) == 0) { // c is a factor
is = false;
break;
}
}
return is;
}
If you need to generate primes, simply iterate through your range of numbers until a sufficient number of primes is generated. You could alternatively change this to return a vector and push the factors in if you wanted to for some other assignment.
bool isPrime(int n) {
if (n <= 1)
return false;
bool is = true;
for (int c = 2; c <= (n / 2); c++) { // lul sepples
if ((n % c) == 0) { // c is a factor
is = false;
break;
}
}
return is;
}
Name:
Anonymous2008-12-11 13:45
>>29
Close, but not n/2, rather sqrt(n) as the upper limit.
Also just test with all previously discovered primes, not every integer.
Name:
Anonymous2008-12-11 14:13
>>29
>Thus, you only need to look for factors prior to n / 2.
sqrt( n )
Name:
Anonymous2008-12-11 18:47
>>31 Also just test with all previously discovered primes, not every integer.
Don't do this, you might miss one of the factors.
Name:
Anonymous2008-12-11 18:57
>>33
You won't get a complete factorization, but that's not what is wanted. If a number is composite, one of its factors will be a prime no larger than its square root; so if you get no factors, the number has to be prime.
This uses the Sieve of Eratosthenes and an assload of memory for speed purposes. It can be further optimized, but this version gets the point across.
I look forward to having it submitted to entry level C/C++ classes across the nation.
int main (int argc, char *argv[])
{
int m, index;
unsigned long size;
_Bool *primes;
// Check supplied arguments
if (argc < 2)
{
fprintf (stderr, "No maximum size specified, using 1,000,000...\n");
size = 1000000;
}
else
{
if (isNumeric (argv[1]))
size = atoi (argv[1]);
else
{
fprintf (stderr, "Maximum size must be numeric.\n");
return 1;
}
}
// Allocate a zeroed block of memory
primes = (_Bool *) calloc (size, sizeof(*primes));
if (primes == NULL)
{
fprintf (stderr, "Failed to allocate enough memory, maximum size too large!\n");
return 1;
}
// Main loop
printf ("Calculating primes for digits 0 -> %i...\n\n", size);
for (index = 2; index < size; index++)
{
if (primes[index] == 0)
{
printf ("%i\n", index);
for (m = 2 * index; m < size; m += index)
primes[m] = 1;
}
}
free (primes);
printf ("\nFinished calculating primes for digits 0 -> %i\n", size);
return 0;
}
// Determines if a character string is numeric
_Bool isNumeric (char str[])
{
int i;
for (i = 0; i < strlen(str); i++)
{
if (!isdigit (str[i]))
return 0;
}
return 1;
}
Name:
Anonymous2008-12-11 21:28
_Bool?
What the fuck.
Name:
Anonymous2008-12-12 2:45
>>35
It's a trivial deduction from the Sieve of Eratosthenes; or you get it by simple induction.
If a number is composite one of its factors is a number less than its square root. Either that factor is prime, in which case the assertion is proved, or composite, in which case we repeat the process on that factor. Since the sequence is strictly monotonic and bounded below, the decomposition must terminate.
Name:
Anonymous2008-12-12 4:06
>>38
In English please, lol. I understood 'factor' and 'prime', but not much else. One hint I learnt from an interviewer was try to explain it to your grandmother, or your 5 year old niece.
Name:
Anonymous2008-12-12 4:45
>>39
Your grandmother and your 5 year old niece haven't read SICP.