Find Prime Numbers using time.h in C

In summary, the first algorithm uses the concept beyond the ancient sieve of eratosthenes, while the second uses the function called isprime(). The first algorithm is faster, but the second might be more accurate.
  • #1
Kalouste
21
0
I've written an algorithm that has the following goal: finding all prime numbers up to a specified integer. I've made two different algorithms actually: on one hand, I've used the concept beyond the ancient sieve of eratosthenes; on the other, I've used a function called isprime() that tests if a number is prime. For instance, let's say I want to determine which method is faster. So I need to time a piece of code in each algorithm.

As an example, here's the code of the first algorithm:

Code:
#include <stdio.h>
#include <math.h>
#include <time.h>

int isprime(int num);

int main () {
int n, num;
time_t t1, t2;

printf("Enter a number\n");

while (scanf("%d", &n) != 1) {
printf("Error: Try again.\n");
	while (getchar() != '\n')
		;
		}

printf("Prime numbers\n");

time(&t1);

for (num = 2; num <= n; num += 1) {
if (isprime(num) == 1)
printf("%d\n", num);

}

time(&t2); 
printf("Time elapsed: %f ms\n", (float)(t2-t1));

return 0;
}

I've omitted the isprime() function definition, because I felt it's unnecessary. The problem with this approach is that my computer writes the numbers so rapidly that I probably will need to write the time in milliseconds if I wanted the algorithm to write every prime number up to a small number, as 11. Is there a function that allows me to do that?
Thank you on advance.

Links I've consulted

"[URL
 
Last edited by a moderator:
Technology news on Phys.org
  • #2
There is the clock() function. But if you want really accurate timing, your best bet is to do one of the following: (I think (1) is the most reliable)

(1) Wrap your code in a loop and repeat it a few thousand times (or million, as necessary), so that the elapsed time is measured in seconds or minutes.

(2) Use a profiling tool.

(3) Try and find an API for the high-performance timer provided by your operating system.



Incidentally, there are two problems with your code:
(1) Printing the primes to screen is probably more time-consuming than the calls to isprime().

(2) On the final printf(...) call, you told it to print an int value (%d), but passed it a float.
 
  • #3
Note though that the clock() function measures the cpu time not the elapsed time.
 
  • #4
(2) On the final printf(...) call, you told it to print an int value (%d), but passed it a float.
Sorry for that, didn't notice.

About the clock() function I will try to use it. I found an interesting thread about that function http://www.thescripts.com/forum/thread213478.html" . When I come up with a fully functional solution I will post it. The (3) solution will also be considered. I didn't know about the existence of 'profiling tools', so I just learned something. Thank you for the suggestions.
 
Last edited by a moderator:
  • #5
you have figured out by now, if not maybe this can help

Code:
#include <ctime>

clock_t cstart = clock();
...
clock_t cend = clock();

double millis = 1000.0 * (cend - cstart) / CLOCKS_PER_SEC;
 
  • #6
The clock() function returns, as MeJennifer stated before, the cpu time which is less than the elapsed time (recall Hurkyl's post: 'Printing the primes to screen is probably more time-consuming than the calls to isprime()'). So I tried this solution, which seems to work although it's not extremely accurate, as one could desire (nor is the clock() function: it returns 0.00000 s cpu time if the computation is done too fast):

Code:
#include <sys/times.h>
#include <sys/wait.h>

  static clock_t st_time;
  static clock_t en_time;
  static struct tms st_cpu;
  static struct tms en_cpu;

  st_time = times(&st_cpu);
  ...
  en_time = times(&en_cpu);

printf("Time elapsed: %ld ms\n", (en_time - st_time));

Example: Print all primes up to 200.
Cpu_time: 0.000000 s
Time elapsed: 0 s (using <time.h>)
Time elapsed: 15 ms (using struct)

http://www.codeproject.com/csharp/highperformancetimercshar.asp"
 
Last edited by a moderator:

Related to Find Prime Numbers using time.h in C

What is the purpose of using time.h in C to find prime numbers?

The time.h library in C allows for the measurement of the execution time of a program. This can be useful when trying to optimize a program to find prime numbers, as it allows for comparison between different algorithms or implementations.

How can I use time.h in C to find the execution time of my prime number finding program?

To use time.h in C, you can include the library in your program using the #include directive, and then use the clock() function to measure the start and end times of your program. You can then subtract the start time from the end time to find the execution time in clock ticks, which can be converted to seconds by dividing by the value of the constant CLOCKS_PER_SEC.

What is the most efficient algorithm for finding prime numbers using time.h in C?

There is no definitive answer to this question, as the most efficient algorithm can vary depending on the input size and other factors. Some commonly used algorithms for finding prime numbers include the Sieve of Eratosthenes, the Sieve of Atkin, and the Miller-Rabin primality test. It is important to benchmark and compare different algorithms to determine the most efficient one for a specific use case.

Can I use time.h in C to find prime numbers in a multithreaded program?

Yes, you can use time.h in a multithreaded program to measure the execution time of each thread. However, it is important to note that the clock() function measures the CPU time used by a program, so if multiple threads are running on different CPUs, the total execution time may be less than the sum of the individual thread execution times.

Is time.h the only way to measure the execution time of a program in C?

No, there are other methods for measuring the execution time of a program in C, such as using the gettimeofday() function or the clock_gettime() function. These methods may provide more accurate results, but they may also require more advanced programming knowledge to implement.

Similar threads

  • Programming and Computer Science
Replies
28
Views
2K
  • Programming and Computer Science
Replies
1
Views
1K
  • Programming and Computer Science
Replies
7
Views
1K
  • Programming and Computer Science
Replies
2
Views
2K
  • Programming and Computer Science
Replies
9
Views
1K
  • Programming and Computer Science
Replies
14
Views
2K
  • Programming and Computer Science
Replies
4
Views
830
  • Programming and Computer Science
Replies
14
Views
2K
  • Programming and Computer Science
Replies
3
Views
1K
  • Programming and Computer Science
Replies
4
Views
951
Back
Top