processor : 0 vendor_id : GenuineIntel cpu family : 6 model : 23 model name : Intel(R) Core(TM)2 Duo CPU E8400 @ 3.00GHz stepping : 6 cpu MHz : 1998.000 cache size : 6144 KB physical id : 0 siblings : 2 core id : 0 cpu cores : 2 apicid : 0 initial apicid : 0 fpu : yes fpu_exception : yes cpuid level : 10 wp : yes flags : fpu vme de pse tsc msr pae mce cx8 apic sep mtrr pge mca cmov pat pse36 clflush dts acpi mmx fxsr sse sse2 ss ht tm pbe syscall nx lm constant_tsc arch_perfmon pebs bts rep_good aperfmperf pni dtes64 monitor ds_cpl vmx smx est tm2 ssse3 cx16 xtpr pdcm sse4_1 lahf_lm tpr_shadow vnmi flexpriority bogomips : 5994.09 clflush size : 64 cache_alignment : 64 address sizes : 36 bits physical, 48 bits virtual power management: processor : 1 vendor_id : GenuineIntel cpu family : 6 model : 23 model name : Intel(R) Core(TM)2 Duo CPU E8400 @ 3.00GHz stepping : 6 cpu MHz : 1998.000 cache size : 6144 KB physical id : 0 siblings : 2 core id : 1 cpu cores : 2 apicid : 1 initial apicid : 1 fpu : yes fpu_exception : yes cpuid level : 10 wp : yes flags : fpu vme de pse tsc msr pae mce cx8 apic sep mtrr pge mca cmov pat pse36 clflush dts acpi mmx fxsr sse sse2 ss ht tm pbe syscall nx lm constant_tsc arch_perfmon pebs bts rep_good aperfmperf pni dtes64 monitor ds_cpl vmx smx est tm2 ssse3 cx16 xtpr pdcm sse4_1 lahf_lm tpr_shadow vnmi flexpriority bogomips : 5994.32 clflush size : 64 cache_alignment : 64 address sizes : 36 bits physical, 48 bits virtual power management:
Tweet
/*
prime.c by Shining Arcanine at Phoronix forums
prime.c is free software: you can redistribute it and/or modify
it under the terms of the GNU Lesser General Public License as published by
the Free Software Foundation, version 2 of the License, but not any later version.
This program is distributed in the hope that it will be useful,
but WITHOUT ANY WARRANTY; without even the implied warranty of
MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
GNU Lesser General Public License for more details.
You should have received a copy of the GNU Lesser General Public License
along with this program. If not, see <http://www.gnu.org/licenses/>.
*/
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define blocks(len) ((len % (sizeof(unsigned int) << 4) == 0 ) ? \
(len / (sizeof(unsigned int) << 4)) : \
(len / (sizeof(unsigned int) << 4) + 1))
unsigned int * bin_arr_prime (const unsigned int len);
enum {DEFAULT, SILENT, NUM_ONLY} config = DEFAULT;
int main (int argc, char *argv[])
{
unsigned int len, num, bitVal, *arr = NULL, count;
switch(argc)
{
case 2:
if (argc == 2 && sscanf(argv[1], "%u", &len))
break;
case 3:
if (argc == 3 && sscanf(argv[2], "%u", &len))
{
if (strcmp(argv[1], "-s") == 0)
{
config = SILENT;
break;
}
else if (strcmp(argv[1], "-n") == 0)
{
config = NUM_ONLY;
break;
}
else if (strcmp(argv[1], "-d") == 0)
{
printf("Program to find small prime numbers\n");
exit(1);
}
}
default:
printf("Usage: %s [-s|n] INTEGER\n", *argv);
exit(1);
}
arr = bin_arr_prime(len);
count = 0;
/* Check to see if 2 is being tested */
/* If yes, print 2, as even numbers */
/* are not represented in the array */
if (len >= 2)
{
switch(config)
{
case NUM_ONLY:
printf("2\n", num);
break;
case SILENT:
break;
default:
printf("\nNumber 2 is a prime number\n");
count++;
}
count++;
}
/* Loop through Prime Array and Output Primes */
for ( num = 1; num <= len ; ++arr )
{
for ( bitVal = 0x80000000; bitVal > 0 && num <= len; bitVal >>= 1, num += 2 )
{
if ((*arr & bitVal) == bitVal)
{
switch(config)
{
case NUM_ONLY:
printf("%i\n", num);
break;
case SILENT:
count++;
break;
default:
printf("Number %i is a prime number\n", num);
count++;
}
}
}
}
/* Output count of prime numbers */
switch(config)
{
case NUM_ONLY:
break;
case SILENT:
printf("%i prime numbers were found.\n", count);
break;
default:
printf("\n%i prime numbers were found.\n", count);
}
/* Free memory used by prime array */
free(arr - blocks(len));
return 0;
}
unsigned int * bin_arr_prime (const unsigned int len)
{
unsigned int num, i, j, *arr = (unsigned int*)malloc (blocks(len) * sizeof(unsigned int));
/* Set all bits to 1, except first bit */
memset (arr, 0xFF, blocks(len) * sizeof(unsigned int));
*arr = 0x7FFFFFFF;
/* Loop through arr, to determine primes */
/* from a list of prime canadiates */
/* num is the number being checked for primiality */
for ( num = 3; num * num <= len ; num += 2 )
{
/* Check if a number has already been set to composite */
if ((arr[num >> 6] & (0x80000000 >> ((num & 0x3E) >> 1))) == 0)
{
continue;
}
/* Loop through all odd mutiples of number and set to composite */
/* Ignoring those mutiples that were already set to composite on */
/* earlier iterations */
for ( i = num * num, j = num << 1; i <= len ; i += j )
{
arr[i >> 6] &= ~(0x80000000 >> ((i & 0x3E) >> 1));
}
}
return arr;
}
--- t.old 2010-03-06 23:38:48.579241698 -0500
+++ t.c 2010-03-06 23:37:39.074240092 -0500
@@ -23,7 +23,7 @@
tofind=atoi(argv[1]);
numfound=1;
- primes=malloc(sizeof(long));
+ primes=malloc(sizeof(long)*totest);
primes[0]=2;
totest=2;
@@ -32,7 +32,6 @@
totest++;
if(isprime(totest)) {
numfound++;
- primes=realloc(primes, numfound*sizeof(long));
primes[numfound-1]=totest;
}
}
aaron@debian:~/Desktop/Download$ gcc nth.c -o nth aaron@debian:~/Desktop/Download$ ./nth 1000000 prime number 1000000: 15485863 total time: 9.58 aaron@debian:~/Desktop/Download$ gcc -m32 nth.c -o nth aaron@debian:~/Desktop/Download$ ./nth 1000000 prime number 1000000: 15485863 total time: 3.44
aaron@debian:~/Desktop/Download$ clang nth.c -o nth aaron@debian:~/Desktop/Download$ ./nth 1000000 prime number 1000000: 15485863 total time: 8.97 aaron@debian:~/Desktop/Download$ clang -m32 nth.c -o nth aaron@debian:~/Desktop/Download$ ./nth 1000000 prime number 1000000: 15485863 total time: 3.32
echo "performance" > /sys/devices/system/cpu/cpu0/cpufreq/scaling_governor echo "performance" > /sys/devices/system/cpu/cpu1/cpufreq/scaling_governor
Comment