-
algorithm
I am making a prime number geneerator. The way I am doing it is by incrementing the number and using if statements to filter out the numbers that arent prime. Is there an algorithm to check and see if a number is even, since there are no even primes.
-
nm i use this
if (i%2 != 0)
-
ok. Now I need to eliminate all multiples of 3, anyone have an idea on how to do that?
-
ok i got it. Here is my code. There are only a few little problems in it. Say the user enters 100, the prime numbers stop at 100, but i want 100 primes printed. It also prints 1.
Code:
/**************************************************
Filename: pgen.c
Author: Mike Hartwig
Purpouse: Generate given amount of prime numbers.
Input: Keyboard
Output: Screen
***************************************************/
#include <stdio.h>
#include <stdlib.h>
int main ()
{
int prime_amount; //the amount of primes to generate.
int prime_count = 1;
int prime_answer; // the answer.
printf("Welcome to the Prime Number Generator.\n");
printf("How many prime numbers would you like to generate: ");
scanf("%d", &prime_amount);
printf("Generating %d prime numbers...\n",
prime_amount);
printf("2, 3, 5, 7 ");
do
{
prime_answer = prime_count++;
if(prime_answer % 2 != 0 && prime_answer % 3 != 0 && prime_answer % 5 != 0 && prime_answer % 7 != 0)
{
printf("%d, ", prime_answer);
}
}
while (prime_count < prime_amount);
return (0);
}
-
Why not
Code:
int FindPrime(int iNumberToTest)
{
int iTemp;
//as far as I am concerned 1 is not prime as it
//has no numbers less than it that it is not divisible by
if(iNumberToTest==1) return FALSE;
for(iTemp=2;iTemp<iNumberToTest;iTemp++)// could even use iNumberToTest/2
{
if(iNumberToTest%iTemp==0)
return FALSE;
}
return TRUE;
}
Put that in a while loop, incrementing the number to test until the required amount of primes found.
-
oh here is what i have now.
Code:
/**************************************************
Filename: main.c
Author: Mike Hartwig
Purpouse: Generate given amount of prime numbers.
Input: Keyboard
Output: Screen
***************************************************/
#include <stdio.h>
#include <stdlib.h>
#include <math.h>
int main ()
{
int prime_amount; //the amount of primes to generate.
int prime_count = 3;
int prime_answer; // the answer.
printf("Welcome to the Prime Number Generator.\n");
printf("How many prime numbers would you like to generate: ");
scanf("%d", &prime_amount);
if (prime_amount < 0) //dont print any primes if given amount is less than 0
{
printf("Please Enter A Number Greater Than 0\n");
}
else
{
printf("Generating %d prime numbers...\n", prime_amount);
}
do
{
prime_answer = prime_count++;
if (prime_answer == 2)
{
printf("2 ");
}
if (prime_answer == 3)
{
printf("3 ");
}
if (prime_answer == 5)
{
printf("5 ");
}
if (prime_answer == 7)
{
printf("7 ");
}
if (prime_answer % 2 != 0 && prime_answer % 3 != 0 && prime_answer % 5 != 0 && prime_answer % 7 != 0)
{
printf("%d ", prime_answer);
}
}
while (prime_count <= prime_amount);
return (0); //done
}
You can go ahead and compile it. The only problem is it should generate the given amount of prime numbers, not print prime numbers till it gets to the given amount.
Say you want to print 100 prime numers, mine only prints until it hits the number 97. It should print 100 prime numbers.
-
-
for this if statement:
Code:
if (prime_answer % 2 != 0 && prime_answer % 3 != 0 && prime_answer % 5 != 0 && prime_answer % 7 != 0)
{
printf("%d \n", prime_answer);
}
Is there a way I can exclude 2, 3, 5, and 7 from this, so they get counted for prime_amount?
-
Code:
#include <stdio.h>
#include <stdlib.h>
#include <math.h>
#define MAX_NR_PRIMES 100000
int main(int argc, char* argv[])
{
int nr_primes;
int* primes_found;
int nr_found = 0;
int i, n = 3;
int prime;
int check;
if (argc < 2) {
fprintf(stderr, "Usage: prime [NUMBER_OF_PRIMES]\n");
return EXIT_FAILURE;
}
nr_primes = atoi(argv[1]);
if (nr_primes < 0 || nr_primes > MAX_NR_PRIMES) {
fprintf(stderr, "Invalid usage\n");
return EXIT_FAILURE;
}
primes_found = malloc(nr_primes * sizeof(int));
if (primes_found == NULL) {
fprintf(stderr, "prime: Ran out of memory\n");
return EXIT_FAILURE;
}
primes_found[nr_found++] = 2;
while(nr_found != nr_primes) {
prime = 1;
check = sqrt(nr_found);
for (i = 0; prime && i < check; ++i) {
if (n % primes_found[i] == 0)
prime = 0;
}
if (prime)
primes_found[nr_found++] = n;
n += 2;
}
for (i = 0; i < nr_found; ++i) {
printf("%-5d ", primes_found[i]);
if ((i + 1) % 13 == 0)
putchar('\n');
}
putchar('\n');
free(primes_found);
return 0;
}
-
Here is some really efficient code from the book "Algorithms in C" (I translated the name from German into English, maybe the book´s name is a little different!):
Code:
#define N 100000
int main(void)
{
char p[N];
register unsigned long i;
unsigned long j;
for(i=1;i<N;p[i]=1, i+=2) ;
for(i=2, p[1]=0;j<N/2;i++)
if p[i] for(j=2;j<N/i;j++) p[i*j]=0;
for(i=1;i<MAX;i+=2)
if p[i] printf("%lu\n", i);
return 0;
}
I hope it´s correct. I tried to optimize it a little...
klausi
-
Unreg,
Don't take this the wrong way, I am trying to help. Your approach is incorrect.
You are not thinking general enough. You can write a very long IF() statement but this is not the correct answer. Doing that will not improve your programming. If you need to find 1,000,000 primes it is impossible to write your kind of program. Do not be limited by the scope of the question and look beyond. If you write a good small piece of code it can always be used in a bigger / another program later.
Every answer here is a different approach to the same problem, all seem valid. (though I think I see some minor errors in Klausi's with the char array acting like an int array at points)
The difference is they will work if any number of primes are requested.
Have you learnt functions?
(breaking a progam up into small blocks or 'functions'. A block can be called more than once making for shorter code)
Arrays?
(a number or group of like variables)
Code:
FIND PRIMES
Ask user for number of primes to find (validate)
while(Primes Found<Primes Needed)
{
test number for 'primeness'
if(is prime)
{
print to screen
increase number primes found
}
increase number to test
}//or [do while] is as good/better
exit
-
@novacain:
I took a char array for saving memory. Why should I use an integer, which is at least two times bigger than a char, for a simple flag?
klausi
-
redone klausi's code
just fixed some stuff
Code:
#include <stdio.h>
#define N 100000
#define MAX 20 /* number of primes you want */
int main(void) {
char p[N];
register unsigned long i;
unsigned long j;
for(i=1;i<N;p[i]=1, i+=2) ;
for(i=2, p[1]=0;j<N/2;i++)
if(p[i]) for(j=2;j<N/i;j++) p[i*j]=0;
for(i=1;i<MAX;i+=2)
if(p[i]) printf("%lu\n", i);
return 0;
}
-
I didn't look through your code in detail, but it looks like you increase the counter in you for-loop with 1 per step. Since all even numbers are NOT prime numbers, you can increase with 2 per step instead, so you check these numbers:
1,3,5,7,9,11...
instead of:
1,2,3,4,5...
-
How about doing it something like this?
Code:
#include <stdio.h>
#include <time.h>
#include <math.h>
int prime(int num);/*Returns 1 if num is a prime, 0 if not*/
int main (void)
{
int tested_number = 2;/*Number currently tested*/
int upper_limit = 10000;/*Max number to test*/
double start;
double finish;
printf("***********************************************\n");
printf("* *\n");
printf("* Welcome to the program that finds prime numbers. *\n");
printf("* Current settings gives the numbers between %d and %d *\n",tested_number, upper_limit);
printf("* *\n");
printf("*********************************************\n\n");
start = clock(); /*Set start*/
while(tested_number < upper_limit)/*Counts between tested_number and upper_limit-1*/
{
if(prime(tested_number))/*Calls prime() wish returns 1 if tested_number is a prime*/
{
printf("%d\n",tested_number);
}
tested_number++;
}
finish = clock();/*Set finish*/
/*prints time it toke to calculate prime numbers*/
printf("Task finished in %2.3f seconds\n", (finish - start) / CLOCKS_PER_SEC );
return 0;/* Tell the operating system we did OK */
}
int prime(int num)
{
double max_to_test = sqrt(num);/*Defines the upper limit that needs to be tested*/
int counter = 2;/*Defines the lover limit that needs to be tested*/
int is_a_prime = 1;/*Return value that get changed to 0 if tested number is not a prime*/
while(counter <= max_to_test)/*Count between lower limit and upper limit*/
{
if(num % counter == 0)/*If this is true it is not a prime*/
{
is_a_prime = 0;/*Return 0*/
}
counter++;
}
return is_a_prime;
}