/
genprime.m
77 lines (67 loc) · 1.43 KB
/
genprime.m
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
#import <Foundation/Foundation.h>
#import <math.h>
#import <stdio.h>
#import <stdlib.h>
#import <sys/time.h>
typedef unsigned long prime_t;
@interface GenPrime : NSObject
- (BOOL) isprime:(prime_t)x;
- (prime_t) genprime:(prime_t)max;
@end
@implementation GenPrime
- (BOOL)isprime:(prime_t)x
{
prime_t lim, y;
if (x < 2)
return NO;
if (x == 2)
return YES;
if (x % 2 == 0)
return NO;
if (x < 9)
return YES;
if ((x + 1) % 6 != 0)
if ((x - 1) % 6 != 0)
return NO;
lim = (prime_t)(sqrt((double)x) + 1.0f);
for (y = 3; y < lim; y += 2)
{
if (x % y == 0)
return NO;
}
return YES;
}
- (prime_t) genprime:(prime_t)max
{
prime_t count = 0,
current = 1;
while (count < max)
{
if ([self isprime:current])
count++;
current++;
}
return current - 1;
}
@end
int main(int argc, char **argv)
{
prime_t start = argc > 1 ? atol(argv[1]) : 0,
stop = argc > 2 ? atol(argv[2]) + 1 : 0,
x, last;
struct timeval begin, end;
double duration;
NSAutoreleasePool *pool = [[NSAutoreleasePool alloc] init];
GenPrime *gp = [[[GenPrime alloc] init] autorelease];
for (x = start; x < stop; x += start)
{
gettimeofday(&begin, NULL);
last = [gp genprime:x];
gettimeofday(&end, NULL);
duration = (double)(end.tv_sec - begin.tv_sec) +
((double)(end.tv_usec) - (double)(begin.tv_usec)) / 1000000.0;
printf("Found %8lu primes in %10.5f seconds (last was %10lu)\n", x, (float)duration, last);
}
[pool release];
return 0;
}